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

Time Complexity: Sort a Linked List Using Merge Sort

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to sort a linked list grows as the list gets bigger.

Specifically, how does merge sort handle this task efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func mergeSort(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    middle := getMiddle(head)
    nextToMiddle := middle.next
    middle.next = nil

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

    sortedList := sortedMerge(left, right)
    return sortedList
}

This code splits the linked list into halves recursively and merges sorted halves back together.

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 touches all nodes each time.

How Execution Grows With Input

As the list size doubles, the number of splitting steps grows slowly, but merging touches all nodes each time.

Input Size (n)	Approx. Operations
10	About 10 * 4 = 40
100	About 100 * 7 = 700
1000	About 1000 * 10 = 10,000

Pattern observation: Operations grow roughly as n times log n, meaning growth is faster than linear but much slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit faster than the list size but stays efficient even for large lists.

Common Mistake

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

[OK] Correct: Merge sort splits the list and merges efficiently, touching each node only a few times, so it runs much faster than bubble sort.

Interview Connect

Understanding merge sort on linked lists shows you can handle recursion and linked data well, a skill useful in many coding challenges.

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 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