Merge Sort Algorithm in DSA C - Build from Scratch

Merge Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Merge Sort is a popular method that splits the list into smaller parts, sorts them, and then merges them back together in order.Imagine you have a messy stack of numbered cards and want to arrange them from smallest to largest quickly and neatly.

🎯 Goal: Build a C program that uses the Merge Sort algorithm to sort an array of integers in ascending order.

📋 What You'll Learn

Create an integer array with the exact values: 38, 27, 43, 3, 9, 82, 10

Create an integer variable called array_size to store the size of the array

Write a merge function to combine two sorted halves into one sorted array

Write a mergeSort function to recursively split and sort the array

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Merge Sort is used in many software applications where large amounts of data need to be sorted efficiently, such as databases, search engines, and file systems.

💼 Career

Understanding merge sort helps in technical interviews and is fundamental for roles involving algorithm design, software development, and data processing.

1

Create the initial array

Create an integer array called arr with these exact values: 38, 27, 43, 3, 9, 82, 10.

DSA C

# Your code here

Hint

Use curly braces {} to list the array values exactly as given.

2

Set the array size

Create an integer variable called array_size and set it to the number of elements in arr using sizeof(arr) / sizeof(arr[0]).

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
# Your code here

Hint

Use sizeof operator to calculate the number of elements in the array.

3

Implement merge and mergeSort functions

Write the merge function that merges two sorted halves of the array, and the mergeSort function that recursively splits and sorts the array. Use parameters int arr[], int left, int right for mergeSort and int arr[], int left, int mid, int right for merge.

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int array_size = sizeof(arr) / sizeof(arr[0]);

// Your code here

Hint

Remember to copy the halves into temporary arrays before merging.

Use recursion in mergeSort to split the array.

4

Print the sorted array

Call mergeSort(arr, 0, array_size - 1) to sort the array, then print the sorted elements separated by spaces using a for loop with variable i.

DSA C

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int array_size = sizeof(arr) / sizeof(arr[0]);

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];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

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

// Your code here

Hint

Call mergeSort with left = 0 and right = array_size - 1.

Use a for loop with variable i to print each element followed by a space.

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