Sort a Linked List Using Merge Sort in DSA Javascript - Execution Trace

Concept Flow - Sort a Linked List Using Merge Sort

Start with head of list

↓

Find middle node using slow & fast pointers

↓

Split list into two halves

↓

Recursively sort left half

↓

Merge two sorted halves

↓

Return sorted list head

The list is split into halves recursively until single nodes remain, then merged back in sorted order.

Execution Sample

DSA Javascript

function mergeSort(head) {
  if (!head || !head.next) return head;
  let middle = getMiddle(head);
  let nextToMiddle = middle.next;
  middle.next = null;
  let left = mergeSort(head);
  let right = mergeSort(nextToMiddle);
  return sortedMerge(left, right);
}

This code splits the list, sorts each half recursively, then merges them sorted.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with full list	4 nodes: 4 -> 2 -> 1 -> 3 -> null	head points to 4	4 -> 2 -> 1 -> 3 -> null
2	Find middle node	4 nodes: 4 -> 2 -> 1 -> 3 -> null	slow at 2, fast at 3	4 -> 2 -> 1 -> 3 -> null
3	Split list at middle	Left half: 4 -> 2 -> null; Right half: 1 -> 3 -> null	middle.next = null	Left: 4 -> 2 -> null Right: 1 -> 3 -> null
4	Recursively sort left half	2 nodes: 4 -> 2 -> null	head points to 4	4 -> 2 -> null
5	Find middle of left half	2 nodes: 4 -> 2 -> null	slow at 4, fast at 2	4 -> 2 -> null
6	Split left half	Left: 4 -> null; Right: 2 -> null	middle.next = null	Left: 4 -> null Right: 2 -> null
7	Sort left single node	1 node: 4 -> null	return 4	4 -> null
8	Sort right single node	1 node: 2 -> null	return 2	2 -> null
9	Merge sorted left halves	2 nodes: 4, 2	merge 4 and 2	2 -> 4 -> null
10	Recursively sort right half	2 nodes: 1 -> 3 -> null	head points to 1	1 -> 3 -> null
11	Find middle of right half	2 nodes: 1 -> 3 -> null	slow at 1, fast at 3	1 -> 3 -> null
12	Split right half	Left: 1 -> null; Right: 3 -> null	middle.next = null	Left: 1 -> null Right: 3 -> null
13	Sort left single node	1 node: 1 -> null	return 1	1 -> null
14	Sort right single node	1 node: 3 -> null	return 3	3 -> null
15	Merge sorted right halves	2 nodes: 1, 3	merge 1 and 3	1 -> 3 -> null
16	Merge two sorted halves	4 nodes: 2 -> 4 and 1 -> 3	merge 2->4 and 1->3	1 -> 2 -> 3 -> 4 -> null
17	Return sorted list	4 nodes: 1 -> 2 -> 3 -> 4 -> null	head points to 1	1 -> 2 -> 3 -> 4 -> null
18	Exit	Sorting complete	No pointer changes	Sorted list: 1 -> 2 -> 3 -> 4 -> null

💡 All nodes merged and sorted, recursion ends.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	After Step 16	Final
head	4 -> 2 -> 1 -> 3 -> null	4 -> 2 -> null	4 -> null	2 -> 4 -> null	1 -> 3 -> null	1 -> null	1 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null
middle	2	2	4	4	1	1	1	2
left	4 -> 2 -> 1 -> 3 -> null	4 -> 2 -> null	4 -> null	2 -> 4 -> null	1 -> 3 -> null	1 -> null	1 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null
right	null	1 -> 3 -> null	2 -> null	null	3 -> null	3 -> null	null	null

Key Moments - 3 Insights

Why do we split the list by setting middle.next = null?

Setting middle.next = null breaks the list into two separate halves so recursive calls sort each half independently, as shown in step 3 and step 6.

How does the merge function combine two sorted lists?

The merge compares nodes from each half and links the smaller node first, building a sorted list step by step, as seen in steps 9, 15, and 16.

Why do we stop recursion when head is null or head.next is null?

Because a list with zero or one node is already sorted, so recursion ends early, as shown in steps 7, 8, 13, and 14.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 9?

A 1 -> 3 -> null

B 2 -> 4 -> null

C 4 -> 2 -> null

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

💡 Hint

Check the 'Visual State' column for step 9 in the execution_table.

At which step does the list first split into two halves?

A Step 2

B Step 6

C Step 3

D Step 12

💡 Hint

Look for the first 'Split list at middle' operation in the execution_table.

If the original list had only one node, what would happen in the execution?

A Recursion stops immediately and returns the node

B List splits into two halves

C Merge function is called twice

D Pointer middle moves to null

💡 Hint

Refer to the base case condition in the code and steps 7, 8, 13, 14.

Concept Snapshot

Merge Sort on Linked List:
- Find middle using slow & fast pointers
- Split list into two halves by setting middle.next = null
- Recursively sort each half
- Merge two sorted halves by comparing nodes
- Base case: list with 0 or 1 node is sorted
- Returns sorted linked list head

Full Transcript

This visualization shows how merge sort works on a linked list. We start with the full list and find the middle node using two pointers moving at different speeds. We split the list into two halves by breaking the link at the middle. Each half is sorted recursively until we reach lists with one or zero nodes, which are already sorted. Then, we merge the sorted halves by comparing nodes one by one, building a sorted list. The process repeats until the entire list is sorted. Key steps include splitting the list, recursive sorting, and merging sorted halves. The final output is a sorted linked list.

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