Merge Sort Algorithm in DSA Go - Time & Space Complexity

Time Complexity: Merge Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by merge sort changes as the list size grows.

How does splitting and merging affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 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++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

This code splits the array into halves recursively and merges sorted halves back.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive splitting and merging of arrays.
• How many times: The array is split about log₂(n) times, and merging happens at each level over all elements.

How Execution Grows With Input

Each split divides the array in half, creating about log₂(n) levels. At each level, merging all parts touches all n elements.

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, which grows faster than n but much slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the size of the input but much better than simple sorting methods that check every pair.

Common Mistake

[X] Wrong: "Merge sort is just a simple loop over the array, so it must be O(n)."

[OK] Correct: Merge sort uses recursion and splits the array multiple times, so it does more work than a single loop.

Interview Connect

Understanding merge sort's time complexity helps you explain efficient sorting and recursion, a key skill in many coding interviews.

Self-Check

"What if we changed merge sort to split the array into three parts instead of two? How would the time complexity change?"