Sort a Linked List Using Merge Sort in DSA Java - Time & Space Complexity

Time Complexity: Sort a Linked List Using Merge Sort

O(n log n)

Understanding Time Complexity

We want to understand how long it takes to sort a linked list using merge sort as the list grows.

How does the sorting time change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode mid = getMiddle(head);
    ListNode rightHead = mid.next;
    mid.next = null;
    ListNode left = mergeSort(head);
    ListNode right = mergeSort(rightHead);
    return merge(left, right);
}

This code splits the linked list into halves, sorts each half recursively, and then merges the sorted halves.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursively splitting the list and merging sorted halves.
• How many times: The list is split about log n times, and merging happens n times in total.

How Execution Grows With Input

Each split divides the list into two smaller parts, and merging combines them back.

Input Size (n)	Approx. Operations
10	About 40 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: The operations grow a bit faster than n but much slower than n squared, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a little more than linearly as the list gets bigger, but still efficient for large lists.

Common Mistake

[X] Wrong: "Merge sort on linked list is as slow as bubble sort, so it takes n squared time."

[OK] Correct: Merge sort splits the list and merges in a way that only needs about n log n steps, much faster than n squared.

Interview Connect

Understanding merge sort on linked lists shows you can handle recursion and pointers well, skills useful in many coding problems.

Self-Check

"What if we used quicksort instead of merge sort on the linked list? How would the time complexity change?"

Practice

1. What is the main advantage of using merge sort to sort a linked list compared to quicksort?

easy

A. Merge sort is easier to implement with arrays than linked lists.

B. Quicksort is faster on linked lists because it uses less memory.

C. Merge sort does not require random access and works well with linked lists.

D. Quicksort always sorts linked lists in O(n) time.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support fast random access, so algorithms needing it perform poorly.

2. Step 2: Compare merge sort and quicksort

   Merge sort splits and merges lists using pointers, avoiding random access, making it efficient for linked lists.

3. Final Answer:

   Merge sort does not require random access and works well with linked lists. -> Option C

4. Quick Check:

   Merge sort suits linked lists better than quicksort [OK]

Hint: Merge sort fits linked lists due to pointer-based splitting [OK]

Common Mistakes:

• Thinking quicksort is always faster on linked lists
• Assuming arrays and linked lists behave the same
• Ignoring random access needs

2. Which of the following is the correct base case condition in the merge sort function for a linked list?

easy

A. if (head == null) return head.next;

B. if (head == null || head.next == null) return head;

C. if (head.next == null) return null;

D. if (head == null && head.next == null) return null;

Solution

1. Step 1: Identify base case for recursion

   When the list is empty or has one node, it is already sorted.

2. Step 2: Check condition correctness

   Condition 'head == null || head.next == null' correctly checks for empty or single-node list.

3. Final Answer:

   if (head == null || head.next == null) return head; -> Option B

4. Quick Check:

   Base case returns head if list size ≤ 1 [OK]

Hint: Base case: empty or single node list returns itself [OK]

Common Mistakes:

• Using && instead of || in base case
• Returning null incorrectly for single node
• Not handling empty list properly

3. Given the linked list: 4 -> 2 -> 1 -> 3 -> null, what is the sorted linked list after applying merge sort?

medium

A. 1 -> 2 -> 3 -> 4 -> null

B. 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 3 -> 2 -> 4 -> null

D. 2 -> 1 -> 3 -> 4 -> null

Solution

1. Step 1: Split the list into halves

   Split into (4 -> 2) and (1 -> 3).

2. Step 2: Recursively sort halves and merge

   Sort (4 -> 2) to (2 -> 4), sort (1 -> 3) to (1 -> 3), then merge to (1 -> 2 -> 3 -> 4).

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option A

4. Quick Check:

   Sorted list ascending order [OK]

Hint: Merge sorted halves to get fully sorted list [OK]

Common Mistakes:

• Not splitting list correctly
• Merging without sorting halves
• Mixing node order during merge

4. Identify the error in this merge function snippet for linked lists:

Node merge(Node a, Node b) {
  if (a == null) return b;
  if (b == null) return a;
  if (a.data < b.data) {
    a.next = merge(a.next, b);
    return b;
  } else {
    b.next = merge(a, b.next);
    return a;
  }
}

medium

A. The function does not merge nodes recursively.

B. The base cases do not handle null nodes.

C. The comparison operator should be <= instead of <.

D. The function returns the wrong node after recursion.

Solution

1. Step 1: Analyze return statements

   When a.data < b.data, function should return 'a' but returns 'b' incorrectly.

2. Step 2: Correct return node after recursion

   Return the node chosen as smaller to maintain sorted order; here it should be 'a' or 'b' accordingly.

3. Final Answer:

   The function returns the wrong node after recursion. -> Option D

4. Quick Check:

   Return chosen smaller node to merge correctly [OK]

Hint: Return the smaller node after recursive merge [OK]

Common Mistakes:

• Returning wrong node after recursive call
• Ignoring base cases
• Incorrect comparison operator

5. You have a linked list with nodes: 5 -> 3 -> 8 -> 2 -> 7 -> null. After applying merge sort, what is the correct sorted linked list? Also, explain why merge sort is preferred over bubble sort for this linked list.

hard

A. 2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists.

B. 8 -> 7 -> 5 -> 3 -> 2 -> null; Bubble sort is faster for small lists.

C. 2 -> 3 -> 5 -> 7 -> 8 -> null; Bubble sort is preferred because it is simpler.

D. 5 -> 3 -> 8 -> 2 -> 7 -> null; Merge sort does not work on linked lists.

Solution

1. Step 1: Sort the list using merge sort

   Sorted order is 2 -> 3 -> 5 -> 7 -> 8 -> null after splitting and merging.

2. Step 2: Explain merge sort advantage

   Merge sort is O(n log n) and uses pointers efficiently; bubble sort is O(n²) and inefficient for linked lists.

3. Final Answer:

   2 -> 3 -> 5 -> 7 -> 8 -> null; Merge sort is faster and uses less memory on linked lists. -> Option A

4. Quick Check:

   Sorted list + merge sort efficiency [OK]

Hint: Merge sort is efficient and stable for linked lists [OK]

Common Mistakes:

• Confusing bubble sort as faster
• Incorrect sorted order
• Thinking merge sort can't handle linked lists