Click here to go back to LeetCode summary page.
Problem description is here, or as follows:
Sort a linked list in O(nlogn) time using constant space complexity.
It is a typical merge sort with top-down implementation. It is essentially a divide-and-conquer method: in each sub-probelm, divide the list in half to two sorted sub-lists, and merge them into a single sorted list. In the end, one will come to a situation where there are only two or one nodes in the list, meaning, respectively, each sub-list only has one node or is just empty (none). Therefore the base cases are sorted as is. The merge subroutine “merge2lists” is borrowed from the solution in “Merge Two Sorted Lists” problem, in which the merge can be done with constant space for linked lists. For arrays, merge sort has space complexity of O(N).
Another popular sorting algorithm with average running time complexity of O(Nlog(N)) is quick sort. The algorithm description and a C implementation can be found here. It can do in-place sort for arrays. However, the worst running time can up to O(N^2) if the initial array is not randomly shuffled (almost sorted).