VietMX Staff asked 3 years ago
Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
Note that recursive approach requires Θ(log n) extra space, since you’ll have Θ(log n) calls on the stack when you’re all the way down to merge-sorting a singleton-list. To reduce it to O(1) extra space, you’ll need to change from a recursive “top-down” approach to an iterative “bottom-up” approach.
Implementation
// The main function
public static Node merge_sort(Node head)
{
if(head == null || head.next == null)
return head;
Node middle = getMiddle(head); //get the middle of the list
Node left_head = head;
Node right_head = middle.next;
middle.next = null; //split the list into two halfs
return merge(merge_sort(left_head), merge_sort(right_head)); //recurse on that
}
// Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
Node dummyHead = new Node();
for(Node current = dummyHead; a != null && b != null; current = current.next;)
{
if(a.data <= b.data)
{
current.next = a;
a = a.next;
}
else
{
current.next = b;
b = b.next;
}
}
current.next = (a == null) ? b : a;
return dummyHead.next;
}
// Utility function to get the middle of the linked list
public static Node getMiddle(Node head) {
if (head == null)
return head;
Node slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}