Merge Sort as Divide and Conquer in DSA C - Time & Space Complexity

Time Complexity: Merge Sort as Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time needed by merge sort grows as the list gets bigger.

Specifically, how does splitting and merging affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    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 l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

This code splits the array into halves, sorts each half recursively, then merges them back.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The merge function compares and copies elements to combine two sorted halves.
• How many times: MergeSort calls itself twice on halves, creating a tree of calls with depth about log n.
• Each merge step processes all elements in the current segment once.

How Execution Grows With Input

Each level of splitting does work proportional to n, and there are about log n levels.

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 a bit more than linearly, roughly n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means if the list doubles in size, the work grows a bit more than double, because of the splitting and merging steps.

Common Mistake

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

[OK] Correct: Merge sort splits the array many times and merges at each level, so the total work adds up to more than just one pass.

Interview Connect

Understanding merge sort's time complexity shows you how divide and conquer helps solve problems efficiently, a key skill in many coding challenges.

Self-Check

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