Merge Sort Algorithm in DSA C++ - Build from Scratch

Merge Sort Algorithm

📖 Scenario: You have a list of numbers that you want to sort in ascending order. Sorting helps you organize data so you can find things faster, like sorting books by title on a shelf.

🎯 Goal: Build a program that uses the merge sort algorithm to sort a list of integers step-by-step. You will first create the list, then set up helper variables, write the merge function, and finally print the sorted list.

📋 What You'll Learn

Create an integer array with exact values

Create helper variables for array size

Write a merge function to combine two sorted halves

Write the mergeSort function to recursively sort the array

Print the sorted array after sorting

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing contacts, searching data quickly, or preparing data for reports.

💼 Career

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

1

Create the array to sort

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

DSA C++

# Create the array arr with the given values
// Your code here

Hint

Use C++ array syntax with curly braces and commas.

2

Set up the array size variable

Create an integer variable called n and set it to the size of arr using sizeof(arr) / sizeof(arr[0]).

DSA C++

int arr[] = {38, 27, 43, 3, 9, 82, 10};
// Create variable n for array size
// Your code here

Hint

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

3

Write the merge function

Write a function called merge that takes arr, left, mid, and right as parameters. This function should merge two sorted halves of the array from left to mid and from mid+1 to right into a sorted segment.

DSA C++

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

// Write the merge function below
// Your code here

Hint

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

4

Write mergeSort and print the sorted array

Write a recursive function called mergeSort that takes arr, left, and right as parameters. It should split the array and call merge to sort. Then call mergeSort(arr, 0, n - 1) and print the sorted array elements separated by spaces.

DSA C++

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

void merge(int arr[], int left, int mid, int right) {
    // merge function code
}

// Write mergeSort function and print sorted array below
// Your code here

Hint

Use recursion to split the array and merge sorted halves. Then print all elements separated by spaces.

Practice

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

easy

A. Select the smallest element and place it at the beginning

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

C. Sort the array by repeatedly swapping adjacent elements

D. Build a heap and extract elements in sorted order

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, Sort, Merge [OK]

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

Common Mistakes:

• Confusing merge sort with bubble sort
• Thinking merge sort swaps adjacent elements
• Mixing merge sort with selection sort

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

easy

A. int mergeSort(int arr[], int left, int right);

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

C. void mergeSort(int arr[], int left, int right);

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

Solution

1. Step 1: Identify the merge function role

   The merge function combines two sorted parts; it does not return a value, so it should be void.

2. Step 2: Check parameter list

   It takes the array and three indices: left, mid, and right to merge subarrays.

3. Final Answer:

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

4. Quick Check:

   Merge function = void with arr and indices [OK]

Hint: Merge combines parts, returns nothing [OK]

Common Mistakes:

• Using int return type for merge
• Confusing merge with mergeSort function
• Wrong parameter order or missing parameters

3. What will be the output of the following code snippet after applying merge sort on the array?

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

medium

A. 5 2 9 1

B. 9 5 2 1

C. 1 2 5 9

D. 2 1 5 9

Solution

1. Step 1: Apply merge sort on the array

   The array {5, 2, 9, 1} is split and sorted recursively to {1, 2, 5, 9}.

2. Step 2: Print the sorted array

   The for loop prints elements in sorted order: 1 2 5 9.

3. Final Answer:

   1 2 5 9 -> Option C

4. Quick Check:

   Sorted array = 1 2 5 9 [OK]

Hint: Merge sort outputs sorted array ascending [OK]

Common Mistakes:

• Printing original array without sorting
• Confusing merge sort with reverse sort
• Off-by-one errors in indices

4. Identify the error in the following merge sort code snippet:

void merge(int arr[], int left, int mid, int right) {
  int n1 = mid - left;
  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];
  // merging logic...
}

medium

A. Incorrect calculation of n1 and n2 sizes

B. Wrong indexing in copying elements to L array

C. Using variable-length arrays which is invalid in C++

D. Missing return statement in void function

Solution

1. Step 1: Check size calculations

   n1 = mid - left is missing +1 (should be mid - left + 1) to include the mid element; n2 = right - mid is correct.

2. Step 2: Check copying to L array

   Copying starts at left + i for i < n1, which goes up to mid-1, missing arr[mid].

3. Step 3: Identify the main error

   The error causes wrong indexing/range when copying elements to L array.

4. Final Answer:

   Incorrect calculation of n1 and n2 sizes -> Option A

5. Quick Check:

   Subarray size calculation off by one [OK]

Hint: Check array copy indices carefully [OK]

Common Mistakes:

• Off-by-one errors in subarray sizes
• Using variable-length arrays in C++
• Ignoring void function return type

5. Given an array with many duplicate elements, how can merge sort be adapted to maintain the relative order of equal elements (stable sort)?

hard

A. Always pick the element from the left subarray first when merging equals

B. Always pick the element from the right subarray first when merging equals

C. Swap equal elements randomly during merge

D. Use quicksort instead of merge sort

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in their original relative order.

2. Step 2: Apply stability in merge step

   When merging, if elements are equal, always choose the element from the left subarray first to keep order.

3. Final Answer:

   Always pick the element from the left subarray first when merging equals -> Option A

4. Quick Check:

   Stable merge = left element first on equals [OK]

Hint: Pick left element first on ties to keep order [OK]

Common Mistakes:

• Picking right element first breaks stability
• Random swaps destroy order
• Confusing merge sort with quicksort stability