C++ Program to Implement Merge Sort using Templates

In this post, we will discuss how to implement merge sort using template function in C++.

It is important to understand why we use the template function. Templates promote code usability. A single template function can perform a task on different datatypes. We don’t have a write separate functions for each data type.

Program

#include<iostream>
#include<vector>
using namespace std;

// template function to merge 2 componenets of the array, arr
// the function merges the sorted components [start, mid] and [mid+1, end]
// such that the resultant array is also sorted
// the function uses a temporary variable, temp to store the result
// after that the result is written back to the original array
template<typename T>
void Merge(T arr[], int start, int end)
{

    // x: start index of first half [start, mid]
    // y: start index of second half [mid+1, end]
    // z: start index of temp
    // temp: temporary vector to store the merged array
    int z, x, y, mid;
    vector<T> temp(end -start + 1);
    mid = (start + end) / 2;
    z = 0;
    x = start;
    y = mid + 1;

    while (x <= mid && y <= end)
    {
        if (arr[x] < arr[y])
        {
            temp[z] = arr[x];
            ++x, ++z;
        }
        else
        {
            temp[z] = arr[y];
            ++y, ++z;
        }
    }

    while (x <= mid)
    {
        temp[z] = arr[x];
        ++x, ++z;
    }

    while (y <= end)
    {
        temp[z] = arr[y];
        ++y, ++z;
    }

    // write the merged sequence back to the original array
    for (int i = start; i <= end; ++i)
    {
        arr[i] = temp[i - start];
    }

}

// template function to perform merge sort on array, arr
template<typename T>
void MergeSort(T arr[], int start, int end)
{

    if (start < end)
    {
        int mid = (start + end) / 2;
        MergeSort(arr, start, mid); // merge sort the elements in range [start, mid]
        MergeSort(arr, mid + 1, end); // merge sort the elements in range [mid+1, end]
        Merge(arr, start, end);   // merge the above 2 componenets
    }

}

// Template function to print array
// n: size of arr[]
template<typename T>
void PrintArray(T arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n\n";
}

int main()
{

    int arr[] = { 1, 10, 10, 90, -32, 100, -1, 11, 9, 14, 3, 2, 20, 19 };
    int n = sizeof(arr) / sizeof(int);

    cout << "Array Before Sorting: " << endl;
    PrintArray(arr, n);

    MergeSort(arr, 0, n - 1);

    cout << "Array After Sorting: " << endl;
    PrintArray(arr, n);

}

Output

C++ program to merge sort array using template function

Read
Quick Sort using Template Function
Find all Subset of the array ( using 2 methods )
Right Shift Array by One

Leave comment if you face any problem

Leave a Comment

Your email address will not be published. Required fields are marked *