Merge Sort Algorithm in C++ and Python

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves array, calls itself for the two halves, and then merges the two sorted halves. The Merge() function is used for merging two halves. 

The Merge(array, start, mid, end) is a key process that assumes that array[start..mid] and array[mid+1..end] are sorted and merges the two sorted sub-arrays into one. See the following C++ and python implementation for details.

Read Also:All Sorting Algorithm In C++

Input:

array = {1, 12, 5, 4, 78, 9, 5, 6, 3, 2, 1, 4};

output:

sorted array:

1 1 2 3 4 4 5 5 6 9 12 78

Explanation:

mergeSort(array[], start, end):

If start < end:

Find the middle point to divide the array into two halves:

• middle mid = start+ (end - start) / 2

Call mergeSort for the first half:

• Call mergeSort(array, start, mid)

Call mergeSort for the second half:

• Call mergeSort(array, mid+1, end)

Merge the two halves sorted in steps 2 and 3:

• Call merge(array,start, mid, end)

this is an image from Wikipedia

Implementation:

C++ Implementation:

//c++ program for merge sort

#include <bits/stdc++.h>

using namespace std;

// Merge to subarray of array

// first_array = array[start..mid]

// second_array = array[mid+1..end]

void Merge(vector<int> &array, int start, int mid, int end)

{

    // creating to temp subarray

    vector<int> first_array;

    vector<int> second_array;

    // copy first_array

    for (int i = start; i <= mid; i++)

    {

        first_array.push_back(array[i]);

    }

    // copy second_array

    for (int i = mid + 1; i <= end; i++)

    {

        second_array.push_back(array[i]);

    }

    // index reference

    int i = 0;                        // for first_array

    int j = 0;                        // for second_array

    int main_i = start;               // for main array

    int size_1 = first_array.size();  // size of first_array

    int size_2 = second_array.size(); // size of second_array

    // merge subarray first_array and second_array 

    // into array[start..end]

    while (i < size_1 && j < size_2)

    {

        if (first_array[i] <= second_array[j])

        {

            array[main_i] = first_array[i];

            i++;

        }

        else

        {

            array[main_i] = second_array[j];

            j++;

        }

        main_i++;

    }

    // copy remaining element of first_array

    while (i < size_1)

    {

        array[main_i] = first_array[i];

        i++;

        main_i++;

    }

    // copy remaining element of second_array

    while (j < size_2)

    {

        array[main_i] = second_array[j];

        j++;

        main_i++;

    }

}

// main merge Sort function

void mergeSort(vector<int> &array, int start, int end)

{

    if (start >= end)

    {

        return;

    }

    // finding mid point

    int mid = start + (end - start) / 2;

    // divide

    mergeSort(array, start, mid);

    mergeSort(array, mid + 1, end);

    // conquer

    Merge(array, start, mid, end);

}

// driver code

int main()

{

    // declaring  array

    vector<int> array = {1, 12, 5, 4, 78, 9, 5, 6, 3, 2, 1, 4};

    int n = array.size();

    mergeSort(array, 0, n - 1);

    // array is sorted

    cout << "sorted array:" << endl;

    for (int i = 0; i < n; i++)

    {

        cout << array[i] << ' ';

    }

    cout << endl;

}

Python Implementation:

# python program for merge sort

# Merge to subarray of array

# first_array = array[start..mid]

# second_array = array[mid+1..end]

def Merge(array, start, mid, end):

    # creating to temp subarray

    first_array = []

    second_array = []

    # copy first_array

    for i in range(start, mid+1):

        first_array.append(array[i])

    # copy second_array

    for i in range(mid + 1, end+1):

        second_array.append(array[i])

    # index reference

    i = 0                        # for first_array

    j = 0                        # for second_array

    main_i = start               # for main array

    size_1 = len(first_array)    # size of first_array

    size_2 = len(second_array)   # size of second_array

    # merge subarray first_array and second_array 

    # into array[start..end]

    while i < size_1 and j < size_2:

        if first_array[i] <= second_array[j]:

            array[main_i] = first_array[i]

            i += 1

        else:

            array[main_i] = second_array[j]

            j += 1

        main_i += 1

    # copy remaining element of first_array

    while i < size_1:

        array[main_i] = first_array[i]

        i += 1

        main_i += 1

    # copy remaining element of second_array

    while j < size_2:

        array[main_i] = second_array[j]

        j += 1

        main_i += 1

# main merge Sort function

def mergeSort(array, start, end):

    if start >= end:

        return

    # finding mid point

    mid = start + (end - start) // 2

    # divide

    mergeSort(array, start, mid)

    mergeSort(array, mid + 1, end)

    # conquer

    Merge(array, start, mid, end)

# driver code

# declaring  array

array = [1, 12, 5, 4, 78, 9, 5, 6, 3, 2, 1, 4]

n = len(array)

mergeSort(array, 0, n - 1)

# array is sorted

print("sorted array:")

for i in range(n):

    print(array[i], end=' ')

print()

Output:

sorted array:

1 1 2 3 4 4 5 5 6 9 12 78

Time Complexity: O(N*log N)

Auxiliary Space: O(N)

Read Also:All Sorting Algorithm In python