Sort a Linked List Using Merge Sort in DSA Javascript

Mental Model

Split the list into halves, sort each half, then merge them back in order. Repeat until the whole list is sorted.

Analogy: Imagine sorting a deck of cards by splitting it into smaller piles, sorting each pile, then carefully merging the piles back together in order.

head -> 4 -> 2 -> 1 -> 3 -> null

Dry Run Walkthrough

Input: list: 4 -> 2 -> 1 -> 3 -> null

Goal: Sort the linked list so the nodes are in ascending order

Step 1: Find middle to split list into two halves

4 -> 2 -> null and 1 -> 3 -> null

Why: Splitting helps break down the problem into smaller parts

Step 2: Recursively sort left half: 4 -> 2

2 -> 4 -> null

Why: Sorting smaller parts first makes merging easier

Step 3: Recursively sort right half: 1 -> 3

1 -> 3 -> null

Why: Right half is already sorted or will be sorted similarly

Step 4: Merge sorted halves 2 -> 4 and 1 -> 3

1 -> 2 -> 3 -> 4 -> null

Why: Merging combines sorted lists into one sorted list

Result:

1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA Javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeSort(head) {
  if (!head || !head.next) return head; // base case: 0 or 1 node

  // Find middle using slow and fast pointers
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null; // split list into two halves

  // Recursively sort each half
  const left = mergeSort(head);
  const right = mergeSort(slow);

  // Merge two sorted halves
  return merge(left, right);
}

function merge(l1, l2) {
  const dummy = new ListNode();
  let current = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next; // advance current pointer
  }

  // Attach remaining nodes
  current.next = l1 || l2;
  return dummy.next;
}

// Helper to print list
function printList(head) {
  let curr = head;
  let result = '';
  while (curr) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
}

// Driver code
const head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
console.log('Original list:');
printList(head);
const sortedHead = mergeSort(head);
console.log('Sorted list:');
printList(sortedHead);

if (!head || !head.next) return head; // base case: 0 or 1 node

stop recursion when list is empty or has one node

while (fast && fast.next) { prev = slow; slow = slow.next; fast = fast.next.next; }

find middle node to split list into halves

prev.next = null; // split list into two halves

break list into two separate lists

const left = mergeSort(head); const right = mergeSort(slow);

recursively sort left and right halves

while (l1 && l2) { if (l1.val <= l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; // advance current pointer }

merge two sorted lists by choosing smaller or equal node each step

current.next = l1 || l2;

attach remaining nodes after one list ends

Output

Original list:

4 -> 2 -> 1 -> 3 -> null

Sorted list:

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merged (n operations per merge)

Space: O(log n) due to recursion stack depth from splitting the list

vs Alternative: Compared to bubble sort O(n²), merge sort is much faster for linked lists because it avoids repeated scanning and swapping

Edge Cases

empty list

returns null immediately without error

DSA Javascript

if (!head || !head.next) return head; // base case: 0 or 1 node

single node list

returns the node as is, already sorted

DSA Javascript

if (!head || !head.next) return head; // base case: 0 or 1 node

list with duplicate values

duplicates are kept and sorted correctly

DSA Javascript

while (l1 && l2) { if (l1.val <= l2.val) { ... } else { ... } }

When to Use This Pattern

When you need to sort a linked list efficiently, use merge sort because it works well with linked lists by splitting and merging without random access.

Common Mistakes

Mistake: Not breaking the list into two halves properly causing infinite recursion
Fix: Set prev.next = null after finding middle to split the list

Mistake: Merging lists incorrectly by not advancing pointers properly
Fix: Advance current and the chosen list pointer after attaching a node

Summary

Sorts a linked list by recursively splitting and merging sorted halves.

Use when you want an efficient O(n log n) sort for linked lists.

The key is to split the list into halves, sort each, then merge back in order.

Practice

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

easy

A. Merge sort uses less memory than bubble sort for arrays.

B. Merge sort efficiently handles linked lists without random access.

C. Merge sort sorts elements in place without extra space.

D. Merge sort is the fastest sorting algorithm for small arrays.

Solution

1. Step 1: Understand linked list access

   Linked lists do not support random access, so algorithms relying on index access are inefficient.

2. Step 2: Analyze merge sort suitability

   Merge sort works by splitting and merging lists using pointers, which fits linked lists well without needing random access.

3. Final Answer:

   Merge sort efficiently handles linked lists without random access. -> Option B

4. Quick Check:

   Linked list + merge sort = efficient pointer-based sorting [OK]

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

Common Mistakes:

• Thinking merge sort sorts in place for linked lists
• Confusing merge sort speed with bubble sort
• Assuming random access is needed for merge sort

2. Which of the following is the correct way to split a linked list into two halves in JavaScript for merge sort?

easy

A. Use a for loop to iterate half the length and split at midpoint index.

B. Use array slicing to split the linked list into two arrays.

C. Use recursion to split the list by removing the head each time.

D. Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end.

Solution

1. Step 1: Identify splitting method for linked list

   Since linked lists lack indexes, we use two pointers: slow and fast to find midpoint.

2. Step 2: Explain pointer movement

   Slow pointer moves one node at a time, fast pointer moves two nodes; when fast reaches end, slow is at midpoint.

3. Final Answer:

   Use two pointers: slow moves 1 step, fast moves 2 steps until fast reaches end. -> Option D

4. Quick Check:

   Two-pointer technique splits linked list correctly [OK]

Hint: Use slow/fast pointers to find midpoint in linked list [OK]

Common Mistakes:

• Trying to use array methods on linked lists
• Using loops with indexes on linked lists
• Splitting by removing head repeatedly

3. What will be the output linked list after applying merge sort on the list: 4 -> 2 -> 1 -> 3 -> null?

medium

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

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

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

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

Solution

1. Step 1: Split the list into halves

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

2. Step 2: Recursively sort and merge halves

   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 ascending list = 1->2->3->4 [OK]

Hint: Merge sort outputs sorted ascending linked list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not fully sorting sublists before merging
• Incorrectly splitting the list

4. Given this merge sort code snippet for linked lists, what is the bug?

function mergeSort(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let mid = slow.next;
  slow.next = null;
  let left = mergeSort(head);
  let right = mergeSort(mid);
  return merge(left, right);
}

medium

A. The mid pointer should be slow, not slow.next.

B. Slow pointer should start at head.next, not head.

C. Fast pointer should start at head.next, not head.

D. The base case should check only for head.next, not head.

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starting at head causes incorrect midpoint for even length lists.

2. Step 2: Correct mid pointer assignment

   The mid pointer should be slow, not slow.next, to correctly split the list into two halves.

3. Final Answer:

   The mid pointer should be slow, not slow.next. -> Option A

4. Quick Check:

   Mid pointer assignment = slow for correct split [OK]

Hint: Mid pointer must be slow for correct split [OK]

Common Mistakes:

• Starting fast pointer at head
• Misplacing mid pointer assignment
• Incorrect base case conditions

5. You have a linked list with nodes containing duplicate values: 3 -> 1 -> 2 -> 3 -> 2 -> null. After applying merge sort, what will be the correct sorted linked list?

hard

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

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

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

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

Solution

1. Step 1: Understand merge sort handles duplicates

   Merge sort compares node values and merges them in ascending order, preserving duplicates.

2. Step 2: Sort and merge duplicates

   Sorting 3->1->2->3->2 results in 1->2->2->3->3 as duplicates remain in sorted order.

3. Final Answer:

   1 -> 2 -> 2 -> 3 -> 3 -> null -> Option C

4. Quick Check:

   Duplicates sorted and preserved in ascending order [OK]

Hint: Merge sort keeps duplicates sorted in order [OK]

Common Mistakes:

• Removing duplicates by mistake
• Sorting incorrectly in descending order
• Confusing linked list with array sorting