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.

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 recursively and merges them back in sorted order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Merging two sorted halves by comparing elements.
• How many times: Merge is called once per level of recursion, and recursion depth is about log n.
• Each merge processes all elements in the current segment once.

How Execution Grows With Input

Each level of recursion processes all elements once during merging.

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, so doubling input size increases work more than double but less than square.

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 slower than checking every pair.

Common Mistake

[X] Wrong: "Merge sort is as slow as bubble sort because it compares elements repeatedly."

[OK] Correct: Merge sort splits the list and merges in a way that only compares elements once per merge step, making it much faster than bubble sort's repeated comparisons.

Interview Connect

Understanding merge sort's time complexity shows you can analyze recursive divide-and-conquer algorithms, 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?"

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Insert elements one by one into a sorted sublist

B. Divide the array into halves, sort each half, then merge them

C. Select a pivot and partition the array around it

D. Sort the array by repeatedly swapping adjacent elements

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   It then merges these sorted halves to produce a fully sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option B

4. Quick Check:

   Merge Sort = Divide and conquer [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses a pivot like Quick Sort
• Believing Merge Sort sorts in place without extra space

2. Which of the following is the correct way to declare the merge function header in C for Merge Sort?

easy

A. void merge(int arr[], int left, int mid, int right);

B. int merge(int arr, int left, int mid, int right);

C. void merge(int arr, int left, int mid, int right);

D. int merge(int arr[], int left, int right);

Solution

1. Step 1: Check parameter types for merge function

   The array should be passed as int arr[] and indices as integers.

2. Step 2: Confirm return type

   Merge function usually returns nothing (void) as it modifies the array in place.

3. Final Answer:

   void merge(int arr[], int left, int mid, int right); -> Option A

4. Quick Check:

   Correct signature = void merge(int arr[], int left, int mid, int right); [OK]

Hint: Array as int arr[], return void for merge [OK]

Common Mistakes:

• Passing array as int arr instead of int arr[]
• Using int return type instead of void
• Missing the mid parameter needed for merging

3. What will be the output of the following code snippet after calling mergeSort(arr, 0, 4); on int arr[] = {5, 3, 8, 4, 2};?

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);
    }
}

medium

A. [3, 5, 4, 2, 8]

B. [5, 3, 8, 4, 2]

C. [2, 3, 4, 5, 8]

D. [8, 5, 4, 3, 2]

Solution

1. Step 1: Understand recursive splitting

   The array is split into halves recursively until single elements remain: [5,3,8,4,2] -> [5,3,8] and [4,2], then further splits.

2. Step 2: Merge sorted halves step-by-step

   After sorting and merging, the final array becomes sorted in ascending order: [2, 3, 4, 5, 8].

3. Final Answer:

   [2, 3, 4, 5, 8] -> Option C

4. Quick Check:

   Sorted array = [2,3,4,5,8] [OK]

Hint: Merge Sort always returns sorted array ascending [OK]

Common Mistakes:

• Assuming original array remains unchanged
• Confusing mergeSort with other sorting algorithms
• Forgetting to merge after recursive calls

4. Identify the error in the following merge function snippet used in Merge Sort:

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++];
}

medium

A. The array sizes n1 and n2 are calculated incorrectly

B. The merge function should return an int instead of void

C. The while loops conditions should be i <= n1 and j <= n2

D. The for loops use <= instead of < causing out-of-bounds access

Solution

1. Step 1: Check for loop boundary errors

   The for loops use <= which causes the loop to run one extra time, leading to out-of-bounds array access.

2. Step 2: Correct loop conditions

   Changing <= to < fixes the loops to iterate exactly n1 and n2 times without overflow.

3. Final Answer:

   The for loops use <= instead of < causing out-of-bounds access -> Option D

4. Quick Check:

   Loop boundary off by one = The for loops use <= instead of < causing out-of-bounds access [OK]

Hint: Use <, not <=, for array index loops [OK]

Common Mistakes:

• Using <= in loops causing overflow
• Confusing return type of merge function
• Changing while loop conditions incorrectly

5. Given an array int arr[] = {12, 11, 13, 5, 6, 7};, how many total merge operations will be performed during a full Merge Sort on this array?

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand merge operations count

   For an array of size n, Merge Sort performs n-1 merge operations combining subarrays stepwise.

2. Step 2: Calculate for n=6

   Here, n=6, so total merges = 6 - 1 = 5 merges.

3. Step 3: Count merges carefully

   Levels: - Level 1: 3 merges (pairs of size 1) - Level 2: 2 merges (subarrays of size 2 and 3) Total merges = 3 + 2 = 5 merges.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Count merges per level = 5 [OK]

Hint: Count merges per level, sum all levels [OK]

Common Mistakes:

• Assuming merges = n-1 without counting levels
• Counting only one level of merges
• Confusing merge operations with comparisons