Merge Sort Algorithm in DSA Go

Mental Model

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

Analogy: Imagine sorting a big pile of cards by first dividing them into small piles, sorting each small pile, then carefully combining the piles back into one sorted stack.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]    [3, 9, 82, 10]

Split further:
[38] [27, 43]    [3, 9] [82, 10]

Split until single elements:
[38] [27] [43]    [3] [9] [82] [10]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split list into two halves

[38, 27, 43]    [3, 9, 82, 10]

Why: We break the problem into smaller parts to sort them easily

Step 2: Split left half into [38] and [27, 43]

[38]    [27, 43]    [3, 9, 82, 10]

Why: Keep splitting until each part has one element

Step 3: Split [27, 43] into [27] and [43]

[38]    [27]    [43]    [3, 9, 82, 10]

Why: Single elements are considered sorted

Step 4: Split right half into [3, 9] and [82, 10]

[38]    [27]    [43]    [3, 9]    [82, 10]

Why: Continue splitting the right half

Step 5: Split [3, 9] into [3] and [9]

[38]    [27]    [43]    [3]    [9]    [82, 10]

Why: Single elements are sorted

Step 6: Split [82, 10] into [82] and [10]

[38]    [27]    [43]    [3]    [9]    [82]    [10]

Why: Single elements are sorted

Step 7: Merge [27] and [43] into [27, 43]

[38]    [27, 43]    [3]    [9]    [82]    [10]

Why: Combine sorted parts in order

Step 8: Merge [3] and [9] into [3, 9]

[38]    [27, 43]    [3, 9]    [82]    [10]

Why: Combine sorted parts in order

Step 9: Merge [82] and [10] into [10, 82]

[38]    [27, 43]    [3, 9]    [10, 82]

Why: Combine sorted parts in order

Step 10: Merge [38] and [27, 43] into [27, 38, 43]

[27, 38, 43]    [3, 9]    [10, 82]

Why: Combine sorted parts in order

Step 11: Merge [3, 9] and [10, 82] into [3, 9, 10, 82]

[27, 38, 43]    [3, 9, 10, 82]

Why: Combine sorted parts in order

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into [3, 9, 10, 27, 38, 43, 82]

[3, 9, 10, 27, 38, 43, 82]

Why: Final merge produces fully sorted list

Result:

[3, 9, 10, 27, 38, 43, 82]

Annotated Code

DSA Go

package main

import "fmt"

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++        }
    }
    // Append remaining elements
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    sorted := mergeSort(arr)
    fmt.Println(sorted)
}

if len(arr) <= 1 { return arr }

stop splitting when array has one or zero elements

mid := len(arr) / 2

find middle index to split array

left := mergeSort(arr[:mid])

recursively sort left half

right := mergeSort(arr[mid:])

recursively sort right half

return merge(left, right)

merge two sorted halves into one sorted array

for i < len(left) && j < len(right) { if left[i] < right[j] { ... } else { ... } }

compare elements from left and right to build sorted result

result = append(result, left[i:]...)

append remaining elements from left if any

result = append(result, right[j:]...)

append remaining elements from right if any

Output

[3 9 10 27 38 43 82]

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because extra space is needed to hold merged arrays during the process

vs Alternative: Compared to simple sorting like bubble sort (O(n²)), merge sort is much faster for large lists but uses extra memory

Edge Cases

empty list

returns empty list immediately without error

DSA Go

if len(arr) <= 1 { return arr }

single element list

returns the single element list as is

DSA Go

if len(arr) <= 1 { return arr }

list with duplicate elements

duplicates are kept and sorted correctly

DSA Go

for i < len(left) && j < len(right) { if left[i] <= right[j] { ... } else { ... } }

When to Use This Pattern

When you need to sort large lists efficiently and can use extra space, look for merge sort because it splits and merges to keep sorting fast.

Common Mistakes

Mistake: Not stopping recursion when array length is 1 or 0, causing infinite recursion
Fix: Add base case: if len(arr) <= 1 { return arr }

Mistake: Merging arrays incorrectly by not handling leftover elements
Fix: After main merge loop, append remaining elements from left and right arrays

Summary

It sorts a list by splitting it into smaller parts, sorting those, and merging them back.

Use it when you want a reliable, efficient sort especially for large lists.

The key is breaking the problem down into smaller sorted pieces and combining them carefully.