C++ Program to Implement Merge Sort

Program to Implement Merge Sort


#include <iostream>

using namespace std;

void Merge(int *arr, int first, int last, int mid)

{

  int i, j, k, temparr[first-last+1];

  i = first;

  k = 0;

  j = mid + 1;

  // Merge into temparr[].

  while (i <= mid && j <= last)

  {

    if (arr[i] < arr[j])

    {

      temparr[k] = arr[i];

      k++;

      i++;

    }

    else

    {

      temparr[k] = arr[j];

      k++;

      j++;

    }

  }

  // Insert remaining values from i to mid into temparr[].

  while (i <= mid)

  {

    temparr[k] = arr[i];

    k++;

    i++;

  }

  // Insert remaining values from j to high into temparr[].

  while (j <= last)

  {

    temparr[k] = arr[j];

    k++;

    j++;

  }

  // Assigning sorted data from temprr[] to arr[].

  for (i = first; i <= last; i++)

  {

    arr[i] = temparr[i-first];

  }

}

// spliting array into two parts.

void MergeSort(int *a, int first, int last)

{

  int mid;

  if (first < last)

  {

    mid=(first+last)/2;

    // Spliting the data into two half.

    MergeSort(a, first, mid);

    MergeSort(a, mid+1, last);

    // Merging elements to get sorted output.

    Merge(a, first, last, mid);

  }

}

int main()

{

  int num, i;

  cout<<"\nHow many number of elements do want to sort: ";

  cin>>num;

int arr[num];

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

  {

    cout<<"Enter the element "<<i+1<<": ";

    cin>>arr[i];

  }

  MergeSort(arr, 0, num-1);

  // Printing the sorted data.

  cout<<"\n Sorted Elements after merge sort are ";

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

cout<<"->"<<arr[i];

  return 0;

}

Output:-

 


Leave a Reply

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