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.