guaranteed to be linearithmic.) During each iteration, natural merge sort works by scanning the list from the left to right identifying naturally sorted sub-lists and merging the sub-lists, and continue
In Java:

Implement a natural merge sort for linked lists. (This is the method of choice for sorting linked lists because it uses no extra space and is guaranteed to be linearithmic.)

During each iteration, natural merge sort works by scanning the list from the left to right identifying naturally sorted sub-lists and merging the sub-lists, and continue scanning further identifying and merging the sub-lists until the end of the list. Repeats the process until the entire list is sorted.

Example:

Unsorted list: M -> E -> R -> G -> E -> S -> O -> R -> T -> E -> X -> A -> M -> P -> L -> E

Sorted list: A -> E -> E -> E -> E -> G -> L -> M -> M -> O -> P -> R -> R -> S -> T -> X