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

Concept Flow - Sort a Linked List Using Merge Sort

Start with head node

↓

Check if list has 0 or 1 node?

Yes→Return head (already sorted)

No↓

Split list into two halves

↓

Recursively sort left half

↓

Merge two sorted halves

↓

Return merged sorted list

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

Execution Sample

DSA Go

func mergeSort(head *Node) *Node {
 if head == nil || head.next == nil {
  return head
 }
 left, right := splitList(head)
 left = mergeSort(left)
 right = mergeSort(right)
 return merge(left, right)
}

This code sorts a linked list by splitting it recursively and merging sorted halves.

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	Split list into halves	Left half: 4->2->null, Right half: 1->3->null	mid pointer at 2, split at 2.next = null	Left: 4 -> 2 -> null | Right: 1 -> 3 -> null
3	Recursively sort left half	2 nodes: 4->2->null	head points to 4	4 -> 2 -> null
4	Split left half	Left: 4->null, Right: 2->null	mid pointer at 4, split at 4.next = null	Left: 4 -> null | Right: 2 -> null
5	Sort left-left half (single node)	1 node: 4->null	head points to 4	4 -> null
6	Sort left-right half (single node)	1 node: 2->null	head points to 2	2 -> null
7	Merge left halves (4 and 2)	2 nodes merged	4.next changed to null, 2.next changed to 4	2 -> 4 -> null
8	Recursively sort right half	2 nodes: 1->3->null	head points to 1	1 -> 3 -> null
9	Split right half	Left: 1->null, Right: 3->null	mid pointer at 1, split at 1.next = null	Left: 1 -> null | Right: 3 -> null
10	Sort right-left half (single node)	1 node: 1->null	head points to 1	1 -> null
11	Sort right-right half (single node)	1 node: 3->null	head points to 3	3 -> null
12	Merge right halves (1 and 3)	2 nodes merged	1.next changed to 3, 3.next changed to null	1 -> 3 -> null
13	Merge sorted left and right halves (2->4 and 1->3)	4 nodes merged	Pointers rearranged to 1->2->3->4->null	1 -> 2 -> 3 -> 4 -> null
14	Return fully sorted list	4 nodes sorted	head points to 1	1 -> 2 -> 3 -> 4 -> null
15	End	No further splits or merges	Done	Sorted list: 1 -> 2 -> 3 -> 4 -> null

💡 All nodes merged back into a single sorted list; recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	After Step 12	After Step 13	Final
head	4->2->1->3->null	4->2->null (left), 1->3->null (right)	4->null (left-left), 2->null (left-right)	2->4->null (sorted left)	1->null (right-left), 3->null (right-right)	1->3->null (sorted right)	1->2->3->4->null (merged)	1->2->3->4->null (final sorted)
mid	nil	2 (middle of full list)	4 (middle of left half)	nil	1 (middle of right half)	nil	nil	nil

Key Moments - 3 Insights

Why do we split the list at mid.next = null?

Splitting at mid.next = null breaks the list into two separate halves, so recursive calls sort each half independently (see Step 2 and Step 4 in execution_table).

Why do single-node lists return immediately without further splitting?

A single-node list is already sorted, so recursion stops (Step 5 and Step 6). This prevents infinite recursion and is the base case.

How does merging two sorted halves rearrange pointers?

During merge (Step 7, 12, 13), pointers are updated to link nodes in ascending order, forming a sorted list without creating new nodes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, what is the visual state of the list after merging left halves?

A 4 -> 2 -> null

B 4 -> null

C 2 -> 4 -> null

D 2 -> null

💡 Hint

Check the Visual State column at Step 7 in execution_table.

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

A Step 1

B Step 2

C Step 4

D Step 9

💡 Hint

Look for the first 'Split list into halves' operation in execution_table.

If the original list had only one node, which step would the function return immediately?

A Step 1

B Step 5

C Step 6

D Step 15

💡 Hint

See the base case check in Step 1 where list length is 0 or 1.

Concept Snapshot

Merge Sort on Linked List:
- Base case: 0 or 1 node returns as is
- Split list into two halves by finding middle
- Recursively sort each half
- Merge two sorted halves by pointer rearrangement
- Result is a fully sorted linked list
- No extra arrays needed, works in O(n log n) time

Full Transcript

Merge sort on a linked list works by splitting the list into two halves recursively until each sublist has one or zero nodes. These small lists are already sorted. Then, the algorithm merges these sorted lists back together by rearranging pointers to form a sorted list. The process repeats until the entire list is sorted. The key steps are splitting the list at the middle, recursive sorting of halves, and merging sorted halves. This method is efficient and uses no extra arrays, sorting the list in O(n log n) time.

Practice

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

easy

A. It sorts the list by comparing only the first and last elements.

B. It sorts the list by swapping adjacent nodes only.

C. It uses a simple loop to sort the list in one pass.

D. It does not require extra space for arrays and works efficiently with linked lists.

Solution

1. Step 1: Understand merge sort with linked lists

   Merge sort splits the list into halves recursively and merges sorted halves. It works well with linked lists because it does not need random access.

2. Step 2: Compare with other sorting methods

   Other sorts like quicksort or bubble sort may require extra space or inefficient node access. Merge sort uses pointers efficiently without extra arrays.

3. Final Answer:

   It does not require extra space for arrays and works efficiently with linked lists. -> Option D

4. Quick Check:

   Merge sort suits linked lists due to pointer use, no extra array needed [OK]

Hint: Merge sort fits linked lists as it uses pointers, no arrays needed [OK]

Common Mistakes:

• Thinking merge sort swaps adjacent nodes only
• Assuming merge sort sorts in one pass
• Believing merge sort compares only first and last elements

2. Which of the following Go function signatures correctly represents the merge function used in merge sort for linked lists?

easy

A. func merge(left []int, right []int) []int

B. func merge(left *Node, right *Node) *Node

C. func merge(left Node, right Node) Node

D. func merge(left *Node, right *Node) int

Solution

1. Step 1: Identify parameter types for linked list nodes

   Linked lists use pointers to nodes, so parameters must be pointers: *Node.

2. Step 2: Identify return type for merged list head

   The merge function returns the head pointer of the merged sorted list, so return type is *Node.

3. Final Answer:

   func merge(left *Node, right *Node) *Node -> Option B

4. Quick Check:

   Merge uses pointers and returns pointer to merged list head [OK]

Hint: Merge function uses pointers to nodes and returns pointer head [OK]

Common Mistakes:

• Using value types instead of pointers for nodes
• Returning int instead of node pointer
• Using slices instead of linked list nodes

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

medium

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

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

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

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

Solution

1. Step 1: Split the list recursively

   Split into halves: (4 -> 2) and (1 -> 3). Then split further until single nodes.

2. Step 2: Merge sorted halves

   Merge single nodes in order: 2 -> 4 and 1 -> 3 become 1 -> 2 -> 3 -> 4.

3. Final Answer:

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

4. Quick Check:

   Sorted order is ascending: 1, 2, 3, 4 [OK]

Hint: Merge sort outputs ascending sorted list [OK]

Common Mistakes:

• Confusing merge order and producing descending list
• Not splitting list fully before merging
• Mixing node values during merge

4. In the following Go code snippet for merge sort on a linked list, what is the error?

func mergeSort(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    mid := getMiddle(head)
    left := head
    right := mid.next
    mid.next = nil
    left = mergeSort(left)
    right = mergeSort(right)
    return merge(left, right)
}

func getMiddle(head *Node) *Node {
    slow, fast := head, head.next
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

medium

A. No error; code correctly splits and merges the list.

B. getMiddle should initialize fast as head, not head.next.

C. mid.next = nil should be after recursive calls.

D. mergeSort should return void, not *Node.

Solution

1. Step 1: Analyze getMiddle function

   Fast starts at head.next to find middle node correctly for even length lists.

2. Step 2: Check mergeSort logic

   Splits list at mid, sets mid.next to nil to break list, recursively sorts left and right, then merges.

3. Final Answer:

   No error; code correctly splits and merges the list. -> Option A

4. Quick Check:

   Code uses standard merge sort steps correctly [OK]

Hint: Check pointer moves carefully; this code matches standard pattern [OK]

Common Mistakes:

• Initializing fast pointer incorrectly causing wrong middle
• Breaking list after recursion causing infinite loops
• Wrong return type for mergeSort function

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

hard

A. 3 -> 3 -> 5 -> 5 -> 8 -> null

B. 5 -> 3 -> 8 -> 3 -> 5 -> null

C. 3 -> 5 -> 8 -> 3 -> 5 -> null

D. 8 -> 5 -> 5 -> 3 -> 3 -> null

Solution

1. Step 1: Understand merge sort handles duplicates

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

2. Step 2: Sort the list step-by-step

   Splitting and merging results in sorted order: 3, 3, 5, 5, 8.

3. Final Answer:

   3 -> 3 -> 5 -> 5 -> 8 -> null -> Option A

4. Quick Check:

   Duplicates appear in sorted order, merge sort preserves all nodes [OK]

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

Common Mistakes:

• Removing duplicates accidentally during merge
• Sorting incorrectly and mixing node order
• Assuming duplicates are removed automatically