CPP Program Merge Sort – Advanced Recursion

by
  • Sort an array A using Merge Sort.
  • Change in the input array itself. So no need to return or print anything.

Input format:

Line 1: Integer n i.e. Array size
Line 2: Array elements (separated by space)

Output format:

Array elements in increasing order (separated by space)

Constraints:

1 <= n <= 1000

Sample Input:

6
2 6 8 5 4 3

Sample Output:

2 3 4 5 6 8

Code:

#include<iostream>
using namespace std;
void merge(int *part1, int size1, int *part2, int size2, int*output, int n)
{
    int i=0;
    int j=0;
    int k=0;
    while(i<size1&&j<size2)
    {
        if(part1[i]<part2[j])
        {
            output[k++]=part1[i++];
        }
        else
        {
            output[k++]=part2[j++];
        }
    }
    while(j<size2)
    {
        output[k++]=part2[j++];
    }
    while(i<size1)
    {
        output[k++]=part1[i++];
    }
}
void mergeSort(int arr[], int size)
{
	if(size==1)
	{
		return;
	}
    int *part1=new int [size/2];
    int size1=size/2;
    int *part2=new int [size-size/2];
    int size2=size-size/2;
    for(int i=0; i<size1; i++)
    {
        part1[i]=arr[i];
    }
    int k=0;
    for(int i=size1; i<size; i++)
    {
        part2[k++]=arr[i];
    }
    mergeSort(part1, size1);
    mergeSort(part2, size2);
    merge(part1, size1, part2, size2, arr, size);
}
int main() {
  int input[1000],length;
  cin >> length;
  for(int i=0; i < length; i++)
    cin >> input[i];
  mergeSort(input, length);
  for(int i = 0; i < length; i++) {
    cout << input[i] << " ";
  }
}
Code language: C++ (cpp)

Leave a Comment