Kata

Linked Lists - Merge Sort

Write a MergeSort() function which recursively sorts a list in ascending order. Note that this problem requires recursion. Given FrontBackSplit() and SortedMerge(), you can write a classic recursive MergeSort(). Split the list into two smaller lists, recursively sort those lists, and finally merge the two sorted lists together into a single sorted list. Return the list.

var list = 4 -> 2 -> 1 -> 3 -> 8 -> 9 -> null
mergeSort(list) === 1 -> 2 -> 3 -> 4 -> 8 -> 9 -> null

FrontBackSplit() and SortedMerge() need not be redefined. You may call these functions in your solution.

These function names will depend on the accepted naming conventions of language you are using. In Python, FrontBackSplit() is actually front_back_split(). In JavaScript, it is frontBackSplit(), etc.

Related Kata in order of expected completion (increasing difficulty):
 Linked Lists - Push & BuildOneTwoThree
 Linked Lists - Length & Count
 Linked Lists - Get Nth Node
Linked Lists - Insert Nth Node
Linked Lists - Sorted Insert
Linked Lists - Insert Sort
Linked Lists - Append
Linked Lists - Remove Duplicates
Linked Lists - Move Node
Linked Lists - Move Node In-place
Linked Lists - Alternating Split
Linked Lists - Front Back Split
Linked Lists - Shuffle Merge
Linked Lists - Sorted Merge
Linked Lists - Merge Sort
Linked Lists - Sorted Intersect
Linked Lists - Iterative Reverse
Linked Lists - Recursive Reverse

Inspired by Stanford Professor Nick Parlante's excellent Linked List teachings.