Sort a Linked List Using Merge Sort in DSA Go

Mental Model

Break the list into smaller parts, sort each part, then join them back in order.

Analogy: Like sorting a deck of cards by splitting it into halves, sorting each half, then merging them back neatly.

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

Dry Run Walkthrough

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

Goal: Sort the linked list so 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 sort smaller parts easily

Step 2: Recursively sort left half (4 -> 2 -> null)

2 -> 4 -> null

Why: Sorting smaller half before merging

Step 3: Recursively sort right half (1 -> 3 -> null)

1 -> 3 -> null

Why: Sorting smaller half before merging

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

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

Why: Merging two sorted lists into one sorted list

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeSort(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head // base case: empty or single node list
	}

	// find middle using slow and fast pointers
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	mid := slow.Next
	slow.Next = nil // split list into two halves

	left := mergeSort(head)   // sort left half
	right := mergeSort(mid)   // sort right half

	return merge(left, right) // merge sorted halves
}

func merge(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	curr := dummy

	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			l2 = l2.Next
		}
		curr = curr.Next
	}

	if l1 != nil {
		curr.Next = l1
	} else {
		curr.Next = l2
	}

	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d", head.Val)
		if head.Next != nil {
			fmt.Printf(" -> ")
		}
		head = head.Next
	}
	fmt.Println(" -> null")
}

func main() {
	// create list 4 -> 2 -> 1 -> 3 -> null
	head := &ListNode{Val: 4}
	head.Next = &ListNode{Val: 2}
	head.Next.Next = &ListNode{Val: 1}
	head.Next.Next.Next = &ListNode{Val: 3}

	fmt.Print("Original list: ")
	printList(head)

	sortedHead := mergeSort(head)

	fmt.Print("Sorted list: ")
	printList(sortedHead)
}

if head == nil || head.Next == nil {

base case: stop when list is empty or has one node

slow, fast := head, head.Next

initialize pointers to find middle

for fast != nil && fast.Next != nil {

move slow one step and fast two steps to find middle

mid := slow.Next slow.Next = nil

split list into two halves at middle

left := mergeSort(head) right := mergeSort(mid)

recursively sort left and right halves

return merge(left, right)

merge two sorted halves into one sorted list

for l1 != nil && l2 != nil {

compare nodes from both lists and link smaller one

if l1 != nil { curr.Next = l1 } else { curr.Next = 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 split in half log n times and merging takes O(n) each time

Space: O(log n) due to recursive call stack for splitting the list

vs Alternative: Compared to bubble or insertion sort on linked list which is O(n²), merge sort is much faster for large lists

Edge Cases

empty list

returns nil immediately without error

DSA Go

if head == nil || head.Next == nil {

single node list

returns the node as is, already sorted

DSA Go

if head == nil || head.Next == nil {

list with duplicate values

duplicates are kept and sorted correctly

DSA Go

for l1 != nil && l2 != nil {

When to Use This Pattern

When asked to sort a linked list efficiently, reach for merge sort because it sorts in O(n log n) time without extra array space.

Common Mistakes

Mistake: Not splitting the list properly causing infinite recursion
Fix: Set slow.Next = nil to break the list into two halves

Mistake: Merging lists incorrectly by not updating pointers properly
Fix: Advance curr pointer after linking a node to keep merging correct

Summary

Sorts a linked list by dividing it into halves, sorting each half, and merging them.

Use when you need an efficient O(n log n) sort on linked lists without extra space.

The key is to split the list into smaller parts and merge sorted parts back together.

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