Merge Sort on Linked List
Merge sort is a natural fit for linked lists because it doesn't require random access. It works by recursively splitting the list into halves and merging sorted halves.
Steps:
1. Find middle (slow-fast pointer).
2. Split list into two halves.
3. Recursively sort each half.
4. Merge two sorted halves.
Merge Sort Implementation
public static Node mergeSort(Node head) {
if (head == null || head.next == null) return head;
// Find middle
Node slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node mid = slow.next;
slow.next = null;
// Recursively sort halves
Node left = mergeSort(head);
Node right = mergeSort(mid);
// Merge sorted halves
return merge(left, right);
}
private static Node merge(Node l1, Node l2) {
Node dummy = new Node(0);
Node tail = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
Two Minute Drill
- Merge sort on linked list is O(n log n) time and O(log n) stack space.
- Ideal for linked lists due to no random access requirement.
- Divides at middle (slow-fast) and merges sorted halves.
- More efficient than quick sort on linked lists.
Need more clarification?
Drop us an email at career@quipoinfotech.com