merge sort implementation in C++

DrRakha

In merge sort we merge two arrays which are already sorted into a larger sorted one. Following code present merge sort example using C++, we describe each section of the code below the code snippet.

Code:

#include <iostream>
using namespace std;
void MergeSort(int* arrayPointer, int firstArrayLimit, int secondArrayLimit);
int main() {
     

    int numbersArray[] = {23, 6, 4, 15, 664, 22, 18,50,2};
    int arraySize = 9;
    // Printing the array
    cout<<" The Array Before Sorting:"<<endl;
    for (int i = 0; i < arraySize; i++){
        cout << numbersArray[i] << "  ";
    }
    cout << endl;
    // Merging Sort
    for (int i = 1; i < arraySize; i *= 2) {

        for (int j = 0; j < arraySize - i; j += 2*i) {
            int subArrayToBeSortedSize = (2*i < arraySize - j) ? 2*i : arraySize - j;
            MergeSort(&(numbersArray[j]), i, subArrayToBeSortedSize);
        }
    }

    // Output sorted array
    cout<<" The Array Sorted:"<<endl;
    for (int i = 0; i < arraySize; i++){
        cout << numbersArray[i] << "  ";
    }
    cout << endl;

    return 0;
}

void MergeSort(int* arrayPointer, int firstArrayLimit, int secondArrayLimit) {
    int i = 0;
    int j = firstArrayLimit;
    int k = 0;
    int* tempArray = new int[secondArrayLimit];
    // Take each next smallest element
    while (i < firstArrayLimit && j < secondArrayLimit) {
        if (arrayPointer[i] < arrayPointer[j]) {
            tempArray[k] = arrayPointer[i];
            ++i;
        } else {
            tempArray[k] = arrayPointer[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (i < firstArrayLimit) {
        tempArray[k] = arrayPointer[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (j < secondArrayLimit) {
        tempArray[k] = arrayPointer[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < secondArrayLimit; ++iIndex) {
        arrayPointer[iIndex] = tempArray[iIndex];
    }
    delete [] tempArray;
}
 

We now look at the important parts that may need hints to be cleared,

To understand the following loop you have first to notice that the input in this example is just a non sorted single array, to deal with such situation every single array element will be considered an array to be merged with the another one , after that every sorted 2 elements array will be merged with another one and so on , that is why (i) step is i*=2. So, for more illustration:
Iteration#1: Merge (1 element sub_array with 1 element sub_array) repeats to all one elements sub_arrays in main array.
Iteration#2: Merge (2 elements sub_array with 2 element sub_array which are already merged and sorted in Iteration#1) repeat to all 2 elements sub_arrays possible in main array.
Iteration#3: Merge (4 elements sub_array with 4 element sub_array which are already merged and sorted in Iteration#1) repeat to all 2 elements sub_arrays possible in main array.

Code:

    for (int i = 1; i < arraySize; i *= 2) {

        for (int j = 0; j < arraySize - i; j += 2*i) {
            int subArrayToBeSortedSize = (2*i < arraySize - j) ? 2*i : arraySize - j;
            MergeSort(&(numbersArray[j]), i, subArrayToBeSortedSize);
        }
    }
 

Following loop is the main and core of the merging sort, where you decide the sub_array which you will select from the next number in the sorted output sequence.

Code:

    while (i < firstArrayLimit && j < secondArrayLimit) {
        if (arrayPointer[i] < arrayPointer[j]) {
            tempArray[k] = arrayPointer[i];
            ++i;
        } else {
            tempArray[k] = arrayPointer[j];
            ++j;
        }
        ++k;
    }
 

Java

C/C++

PHP

C#

HTML

CSS

ASP

Javascript

JQuery

AJAX

XSD

Python

Matlab

R Scripts

Weka

merge sort implementation in C++

Topic Tags