Merge Sort as Divide and Conquer in DSA C++ - Build from Scratch

Merge Sort as Divide and Conquer

📖 Scenario: You have a list of numbers that you want to sort from smallest to largest. Sorting helps you find things faster, like organizing books by their titles on a shelf.

🎯 Goal: You will build a program that uses the merge sort method to sort a list of numbers. Merge sort works by splitting the list into smaller parts, sorting those parts, and then joining them back together in order.

📋 What You'll Learn

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

Create a function called merge that combines two sorted parts of the array

Create a function called mergeSort that splits the array and sorts it using merge

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting is used in many places like organizing files, searching data quickly, and arranging items in online stores.

💼 Career

Understanding merge sort helps in software development roles where efficient data handling and algorithm knowledge are important.

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 int arr[] = {38, 27, 43, 3, 9, 82, 10}; to create the array.

2

Add the merge function

Add a function called merge that takes three integers left, mid, and right and merges the two sorted parts of arr from left to mid and from mid+1 to right into a sorted part.

DSA C++

#include 
using namespace std;

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

void merge(int left, int mid, int right) {
    // Your code here
}

int main() {
    return 0;
}

Hint

Use temporary arrays to hold the left and right parts, then merge them back into arr.

3

Add the mergeSort function

Add a recursive function called mergeSort that takes two integers left and right. It should split the array into halves, call itself on each half, and then call merge to combine them.

DSA C++

#include 
using namespace std;

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

void merge(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 left, int right) {
    // Your code here
}

int main() {
    return 0;
}

Hint

Split the array by finding the middle, then call mergeSort on each half, and finally call merge.

4

Sort and print the array

In main, call mergeSort with left = 0 and right = 6 to sort the entire array. Then print all elements of arr separated by spaces.

DSA C++

#include 
using namespace std;

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

void merge(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 left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }
}

int main() {
    // Your code here
}

Hint

Call mergeSort(0, 6) to sort the whole array, then print each element with a space.

Practice

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

easy

A. Select a pivot and partition the array around it

B. Sort the array by repeatedly swapping adjacent elements

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

D. Insert elements one by one into a sorted list

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

   After splitting, it merges the halves back in sorted order to form the sorted array.

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [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 merging

2. Which of the following is the correct base case condition in a typical Merge Sort implementation in C++?

easy

A. if (start > end) return;

B. if (start < end) return;

C. if (start == end + 1) return;

D. if (start >= end) return;

Solution

1. Step 1: Identify when to stop recursion

   The base case is when the subarray has one or zero elements, meaning start index is greater or equal to end index.

2. Step 2: Match condition to code

   The condition if (start >= end) return; correctly stops recursion when the subarray cannot be divided further.

3. Final Answer:

   if (start >= end) return; -> Option D

4. Quick Check:

   Base case = start >= end [OK]

Hint: Stop recursion when start is not less than end [OK]

Common Mistakes:

• Using start > end misses single element subarray
• Using start == end + 1 is incorrect indexing
• Using start < end returns too early

3. What will be the output of the following C++ code snippet using Merge Sort on array {4, 1, 3, 2}?

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, 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) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main() {
    int arr[] = {4, 1, 3, 2};
    int n = 4;
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    return 0;
}

medium

A. 1 2 3 4

B. 4 3 2 1

C. 1 3 2 4

D. 2 1 3 4

Solution

1. Step 1: Trace recursive splitting and merging

   The array splits into [4,1] and [3,2], then further into single elements. Each pair is merged sorted: [1,4] and [2,3].

2. Step 2: Final merge

   Merging [1,4] and [2,3] results in [1,2,3,4]. The output prints this sorted array.

3. Final Answer:

   1 2 3 4 -> Option A

4. Quick Check:

   Sorted array = 1 2 3 4 [OK]

Hint: Merge Sort always outputs sorted array [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to merge after recursive calls
• Printing array before sorting completes

4. Identify the bug in this Merge Sort merge function snippet:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, 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++];
}

medium

A. The loop 'for (int i = 0; i <= n1; i++)' causes out-of-bounds access

B. The merge condition should be 'L[i] < R[j]' instead of '<='

C. The arrays L and R should be dynamically allocated

D. The indices i and j should start from 1, not 0

Solution

1. Step 1: Check loop bounds for copying left array

   The loop uses 'i <= n1', which runs one extra iteration causing out-of-bounds access since valid indices are 0 to n1-1.

2. Step 2: Correct loop condition

   The loop should be 'i < n1' to copy exactly n1 elements without overflow.

3. Final Answer:

   The loop 'for (int i = 0; i <= n1; i++)' causes out-of-bounds access -> Option A

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Check array loops use < not <= for indexing [OK]

Common Mistakes:

• Using <= instead of < in loops
• Starting indices at 1 instead of 0
• Ignoring dynamic allocation but it's not mandatory here

5. Given an array {5, 3, 8, 6, 2, 7, 4, 1}, how many total merge operations will be performed during a full Merge Sort?

hard

A. 15

B. 7

C. 8

D. 4

Solution

1. Step 1: Understand merge operations in Merge Sort

   Merge Sort splits the array until single elements, then merges pairs stepwise. For n=8 elements, merges happen at each level combining subarrays.

2. Step 2: Calculate total merges

   Number of merges = n - 1 = 8 - 1 = 7 merges in total to combine all elements into one sorted array.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Total merges = n - 1 = 7 [OK]

Hint: Total merges in Merge Sort = array size minus one [OK]

Common Mistakes:

• Counting merges as number of elements
• Confusing merges with recursive calls
• Assuming merges double at each level