Merge Sort Code

 Merge Sort Code

Send Feedback

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 <= 10^3

Sample Input 1 :

6 
2 6 8 5 4 3

Sample Output 1 :

2 3 4 5 6 8

Sample Input 2 :

5
2 1 5 2 3

Sample Output 2 :

1 2 2 3 5 

void mergeTwo(int input[], int start, int mid, int end) {
  int length = end - start + 1;
  int array[length];
  int i = start, j = mid + 1, k = 0;
  for (i = start, j = mid + 1; i <= mid && j <= end;) {
    if (input[i] <= input[j]) {
      array[k] = input[i];
      i++;
      k++;
    } else {
      array[k] = input[j];
      j++;
      k++;
    }
  }
  while (i <= mid) {
    array[k] = input[i];
    i++;
    k++;
  }
  while (j <= end) {
    array[k] = input[j];
    j++;
    k++;
  }
  for (i = start, k = 0; i <= end && k < length; i++, k++) {
    input[i] = array[k];
  }
}
void merge(int input[], int start, int end) {
  // mid, recursion, call function to merge two sorted array
  if (start >= end)
    return;
  int mid = (start + end) / 2;
  merge(input, start, mid);
  merge(input, mid + 1, end);
  mergeTwo(input, start, mid, end);
}
void mergeSort(int input[], int size) { merge(input, 0, size - 1); }

void mergeTwo(int input[], int start, int mid, int end){
    int length = end-start+1;
    int array[length];
    int i = start, j = mid+1, k = 0;
    
    for(i = start, j = mid+1; i <= mid && j <= end;  ){
        if(input[i] <= input[j]){
            array[k] = input[i];
            i++;
            k++;
        }
        else{
            array[k] = input[j];
            j++;
            k++;
        }
    }
    while(i <= mid){
        array[k] = input[i];
        i++;
        k++;
    }
    while(j <= end){
        array[k] = input[j];
        j++;
        k++;
    }
    
    for(i = start, k = 0; i <= end && k < length; i++, k++){
        input[i] = array[k];
    }
}
void merge(int input[], int start, int end){
    //mid, recursion, call function to merge two sorted array
    if(start >= end)
        return;
    int mid = (start+end)/2;
    merge(input, start, mid);
    merge(input, mid+1, end);
    mergeTwo(input, start, mid, end);
}
void mergeSort(int input[], int size){
    merge(input, 0, size-1);
}

#include <iostream>
#include "solution.h"


void mergeTwo(int input[], int start, int mid, int end){
    int length = end-start+1;
    int array[length];
    int i = start, j = mid+1, k = 0;
    
    for(i = start, j = mid+1; i <= mid && j <= end;  ){
        if(input[i] <= input[j]){
            array[k] = input[i];
            i++;
            k++;
        }
        else{
            array[k] = input[j];
            j++;
            k++;
        }
    }
    while(i <= mid){
        array[k] = input[i];
        i++;
        k++;
    }
    while(j <= end){
        array[k] = input[j];
        j++;
        k++;
    }
    
    for(i = start, k = 0; i <= end && k < length; i++, k++){
        input[i] = array[k];
    }
}
void merge(int input[], int start, int end){
    //mid, recursion, call function to merge two sorted array
    if(start >= end)
        return;
    int mid = (start+end)/2;
    merge(input, start, mid);
    merge(input, mid+1, end);
    mergeTwo(input, start, mid, end);
}
void mergeSort(int input[], int size){
    merge(input, 0, size-1);
}




int main() {
  int length;
  cin >> length;
  int* input = new int[length];
  for(int i=0; i < length; i++)
    cin >> input[i];
  mergeSort(input, length);
  for(int i = 0; i < length; i++) {
    cout << input[i] << " ";
  }
}