1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Ascending Order using the Merge Sort algorithm.

Merge Sort is a 'divide and conquer' algorithm that works by continually dividing the unsorted list into n sublists (each containing one element), then repeatedly merging sublists to produce new sorted sublists until there's just one left. The process makes it an efficient and popular sorting method.

2. Program Overview

The C++ program is structured around:

1. merge(): Function to merge two halves of an array.

2. mergeSort(): The recursive function that divides the array and sorts them.

3. printArray(): Utility function to display the array's elements.

4. main(): The main function that initiates the program.

3. Code Program

#include<iostream>
using namespace std;

// Merges two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    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];

    // Merge the temp arrays back into arr[l..r]
    int i = 0;
    int j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[l..r] using merge()
void mergeSort(int arr[], int l, int r) {
    if (l >= r) return; // Base case
    int m = l + (r - l) / 2; // Find the middle point
    mergeSort(arr, l, m); // Sort first half
    mergeSort(arr, m + 1, r); // Sort second half
    merge(arr, l, m, r); // Merge the sorted halves
}

// Utility to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver function
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array: \n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "Sorted array in ascending order: \n";
    printArray(arr, arr_size);
    return 0;
}

Output:

Original array:
12 11 13 5 6 7 
Sorted array in ascending order: 
5 6 7 11 12 13

4. Step By Step Explanation

1. merge(): The purpose of this function is to take two halves of an array and merge them in a sorted order. Temporary arrays L and R are created to hold these two halves.

2. mergeSort(): A recursive function that first divides the array into two halves using a middle point and then sorts these halves. Once sorted, the two halves are merged back together using the merge() function.

3. printArray(): Simply for visualization. Demonstrates the state of the array before and after the sorting.

4. main(): Sets up a sample array, showcases it, runs the merge sort algorithm, and then displays the sorted array.

Merge Sort is widely acknowledged for its guaranteed O(n log n) performance, irrespective of the distribution of input. Its consistent efficiency comes at a slight trade-off of additional memory overhead due to the temporary L and R arrays used during the merging process.

Related C++ Programs on Sorting Algorithms

Related C++ Programs with Output and Step-By-Step Explanation:

Java Guides

Search This Blog

Merge Sort in Ascending Order in C++