Merge Sort Algorithm in DSA C++ - 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.

Specifically, how many steps does merge sort take to sort a list of numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The merge function that combines two sorted halves by comparing elements.
• How many times: Merge is called once for each level of recursion, and recursion depth is about log n.
• Each merge processes all elements in the current segment, so total work per level is proportional to n.

How Execution Grows With Input

As the list size doubles, the number of steps grows a bit more than double but less than square.

Input Size (n)	Approx. Operations
10	About 40 steps
100	About 700 steps
1000	About 10,000 steps

Pattern observation: The steps grow roughly like n times log n, which grows faster than n but slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means if the list size doubles, the time taken grows a bit more than double but much less than square.

Common Mistake

[X] Wrong: "Merge sort is always slower than simple sorting because it uses recursion and extra arrays."

[OK] Correct: Merge sort's smart splitting and merging keep the total steps low, making it faster on large lists than simple methods like bubble sort.

Interview Connect

Understanding merge sort's time complexity shows you can analyze recursive algorithms and compare sorting methods, a key skill in 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?"