LinkedListProblem 27 of 36
Why Quicksort is preferred for Arrays and Merge Sort for LinkedLists
Problem Statement
Given a singly linked list, explain why Merge Sort is preferred over Quick Sort, and implement both styles for interview understanding.
Approach 1: Brute Force (Quick Sort Style on Linked List Data Swaps)
Intuition
Apply quick sort idea on linked list by partitioning around pivot and swapping node values. It works, but partitioning is expensive and can degrade badly.
Algorithm
- Choose end node as pivot
- Partition list segment by moving values less than pivot to left side
- Recursively sort left and right segments
- Return sorted list
java
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
public class Solution {
private Node partition(Node start, Node end) {
int pivot = end.data;
Node p = start, curr = start;
while (curr != end) {
if (curr.data < pivot) {
int t = p.data; p.data = curr.data; curr.data = t;
p = p.next;
}
curr = curr.next;
}
int t = p.data; p.data = end.data; end.data = t;
return p;
}
public void quickSort(Node start, Node end) {
if (start == null || end == null || start == end) return;
Node pivot = partition(start, end);
if (pivot != null && start != pivot) {
Node tmp = start;
while (tmp.next != pivot) tmp = tmp.next;
quickSort(start, tmp);
}
if (pivot != null && pivot.next != null) quickSort(pivot.next, end);
}
}Complexity Analysis
- Time Complexity: O(n^2) - Worst-case partition behavior is common for lists
- Space Complexity: O(log n) average recursion stack
Approach 2: Optimal (Merge Sort on Linked List)
Intuition
Merge sort fits linked list structure: split with slow/fast pointer, then merge by pointer rewiring.
Algorithm
- Find middle of list using slow/fast pointers
- Split into two halves
- Recursively sort both halves
- Merge sorted halves by pointer comparison
java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Solution {
private Node getMiddle(Node head) {
Node slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private Node merge(Node left, Node right) {
Node dummy = new Node(0);
Node tail = dummy;
while (left != null && right != null) {
if (left.data <= right.data) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
tail.next = (left != null) ? left : right;
return dummy.next;
}
public Node mergeSort(Node head) {
if (head == null || head.next == null) return head;
Node middle = getMiddle(head);
Node rightHalf = middle.next;
middle.next = null;
Node left = mergeSort(head);
Node right = mergeSort(rightHalf);
return merge(left, right);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Balanced divide and linear merge each level
- Space Complexity: O(log n) - Recursion stack (merge itself is pointer-based)
Key Takeaways
- Linked lists do not support O(1) random index access.
- Merge sort is stable and naturally pointer-friendly for linked lists.
- In interviews: Array -> Quick/Intro sort, Linked List -> Merge sort.