# Sort List

This is No.148 Problem in LeetCode.

Here are two approaches as below:

##### Top Down Merge Sort
• Recursively split the original list into two halves. The split continues until there is only one node in the linked list (Divide phase). To split the list into two halves, we find the middle of the linked list using the Fast and Slow pointer approach as mentioned in Find Middle Of Linked List.

• Recursively sort each sublist and combine it into a single sorted list. (Merge Phase). This is similar to the problem Merge two sorted linked lists


class Solution {
ListNode right = sortList(mid);
return merge(left, right);
}

ListNode merge(ListNode list1, ListNode list2) {
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 != null) ? list1 : list2;
}

ListNode midPrev = null;
midPrev = (midPrev == null) ? head : midPrev.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}
##### Bottom Up Merge Sort
• Start with splitting the list into sublists of size 11. Each adjacent pair of sublists of size 11 is merged in sorted order. After the first iteration, we get the sorted lists of size 22. A similar process is repeated for a sublist of size 22. In this way, we iteratively split the list into sublists of size 1,2,4,8 ..1,2,4,8.. and so on until we reach nn.

• To split the list into two sublists of given \text{size}size beginning from \text{start}start, we use two pointers, \text{mid}mid and \text{end}end that references to the start and end of second linked list respectively. The split process finds the middle of linked lists for the given \text{size}size.

• Merge the lists in sorted order as discussed in Approach 1

• As we iteratively split the list and merge, we have to keep track of the previous merged list using pointer \text{tail}tail and the next sublist to be sorted using pointer \text{nextSubList}nextSubList.


class Solution {
ListNode tail = new ListNode();
ListNode nextSubList = new ListNode();

for (int size = 1; size < n; size = size * 2) {
while (start != null) {
if (start.next == null) {
tail.next = start;
break;
}
ListNode mid = split(start, size);
merge(start, mid);
start = nextSubList;
}
}
}

ListNode split(ListNode start, int size) {
ListNode midPrev = start;
ListNode end = start.next;
//use fast and slow approach to find middle and end of second linked list
for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
if (end.next != null) {
end = (end.next.next != null) ? end.next.next : end.next;
}
if (midPrev.next != null) {
midPrev = midPrev.next;
}
}
ListNode mid = midPrev.next;
midPrev.next = null;
nextSubList = end.next;
end.next = null;
// return the start of second linked list
return mid;
}

void merge(ListNode list1, ListNode list2) {
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
newTail.next = list1;
list1 = list1.next;
newTail = newTail.next;
} else {
newTail.next = list2;
list2 = list2.next;
newTail = newTail.next;
}
}
newTail.next = (list1 != null) ? list1 : list2;
// traverse till the end of merged list to get the newTail
while (newTail.next != null) {
newTail = newTail.next;
}
// update the old tail to the new tail of merged list
tail = newTail;
}