Answer to Question #253193 in C++ for Tarurendra Kushwah

Question

Write a C/C++ program to sort a list of elements using the merge sort algorithm.

Note: Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Answer 1

#include <iostream>
//**************************************************************
using namespace std;
//**************************************************************
void merge_sort(int* a, int left, int right);
void merge(int* a, int left, int right, int mid);
//**************************************************************
int main()
{
    int size;
    cout << "Enter quantity of elements in array: ";
    cin >> size;
    int* a = new int[size];
    cout << "Enter elements to be sorted (using space): ";
    for (int i = 0; i < size; i++) 
    {
        cin >> a[i];
    }
    merge_sort(a, 0, size - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}
//**************************************************************
void merge_sort(int* a, int left, int right)
{
 
    if (left < right)
    {
        int mid = (left + right) / 2;
        merge_sort(a, left, mid);
        merge_sort(a, mid + 1, right);
        merge(a, left, right, mid);
    }
}
//**************************************************************
void merge(int* a, int left, int right, int mid)
{
    int i, j, k;
    int* temp = new int[right + 1];
    i = left;
    k = left;
    j = mid + 1;
    while (i <= mid && j <= right) 
    {
        if (a[i] < a[j]) 
        {
            temp[k] = a[i];
            k++;
            i++;
        }
        else 
        {
            temp[k] = a[j];
            k++;
            j++;
        }
    }
    while (i <= mid) 
    {
        temp[k] = a[i];
        k++;
        i++;
    }
    while (j <= right) 
    {
        temp[k] = a[j];
        k++;
        j++;
    }
    for (i = left; i < k; i++) 
    {
        a[i] = temp[i];
    }
    delete[]temp;
}
//**************************************************************