Implement Merge Sort using C++

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are specific approaches to solve problems in such a way that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some mediocre programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Binary Merge Sort using C++.

What is Merge Sort?

 

• One of the very efficient sorting algorithms in data structures. Merge Sort is the way of arranging elements in a sequence or ascending order.

 

• Merge sort follows the principles of the divide & conquer Algorithm. The base array is divided into two arrays. And is further divided till the arrangement of elements doesn’t form a sequence.

 

Also Read: Implement Binary Insertion Sort using C++.

 

What’s The Approach?

 

• Firstly we’ll find the midpoint of the array so that we know from where to divide the array.

 

• So let us consider the array, arr[begin..mid..end] .So the first subarray will be leftArray[begin..mid] and the second subarray will be rightArray[mid+1..end]

 

• The above instructions will be executed recursively till there’s only a single element in the subarray.

 

• Once the elements are sorted we’ll merge both the subarrays in ascending order.

 

• The above three instructions will continue to repeat till the entire array is sorted.

 

C++ Program To Implement Merge Sort

 

Input:

 

12, 11, 13, 5, 6, 7

 

Output:

 

Sorted array is: 

 

5 6 7 11 12 13

 

 

// C++ program for Merge Sort
#include <iostream>
using namespace std;

// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid, int const right)
{
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    // Create temp arrays
    auto *leftArray = new int[subArrayOne],
        *rightArray = new int[subArrayTwo];

    // Copy data to temp arrays leftArray[] and rightArray[]
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    auto indexOfSubArrayOne = 0, // Initial index of first sub-array
        indexOfSubArrayTwo = 0; // Initial index of second sub-array
    int indexOfMergedArray = left; // Initial index of merged array

    // Merge the temp arrays back into array[left..right]
    while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}

// begin is for left index and end is
// right index of the sub-array
void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return; // Returns recursively

    auto mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
void printArray(int A[], int size)
{
    for (auto i = 0; i < size; i++)
        cout << A[i] << " ";
}

// Driver code
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    auto arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Given array is \n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}