Merge Sort C++ | Merge Sort Program in C++

Read Similar Posts:

1. Merge Sort in C

2. Merge Sort Time Complexity

Merge Sort Program in C++

//Code Body Start

#include<iostream>

using namespace std;


void Merge(int a[], int left, int mid, int right, int n);

void MergeSort(int a[], int left, int right, int n);


int main()

{

    int i, n, numbers[500];

    cin>>n;

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

    {

        cin>>numbers[i];

    }

    MergeSort(numbers, 0, n-1, n);

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

    {

        cout<<numbers[i]<<" ";

    }

    cout<<endl;

    return 0;

}


void Merge(int a[], int left, int mid, int right, int n)

{

    int leftSize = mid - left + 1, rightSize = right - mid;

    int i, j, k, leftArray[leftSize], rightArray[rightSize];

    for(i=0;i<leftSize;i++)

    {

        leftArray[i] = a[left+i];

    }

    for(i=0;i<rightSize;i++)

    {

        rightArray[i] = a[mid+1+i];

    }

    i = j = 0;

    k = left;

    while(i < leftSize && j < rightSize)

    {

        if(leftArray[i] < rightArray[j])

        {

            a[k++] = leftArray[i];

            i++;

        }

        else

        {

            a[k++] = rightArray[j];

            j++;

        }

    }

    while(i < leftSize)

    {

        a[k++] = leftArray[i];

        i++;

    }

    while(j < rightSize)

    {

        a[k++] = rightArray[j];

        j++;

    }

}

void MergeSort(int a[], int left, int right, int n)

{

    int mid, i;

    if(left < right)

    {

        mid = (left + right) / 2;

        MergeSort(a, left, mid, n);

        MergeSort(a, mid+1, right, n);

        Merge(a, left, mid, right, n);

    }

}


//Code Body End


Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100 /*Numbers*/

Sample Output:
12 33 44 55 66 77 88 99 100 555

Post a Comment

Previous Post Next Post