Merge Sort

Merge Sort is a “Divide and Conquer” algorithm which first divides an input array in two sub-arrays, then it calls itself for those two sub-arrays, orders them and finally merges them into the original array. Write a merge sort program to sort an integer array in ascending order.

Difficulty: Easy.

Input

  • One integer representing the length of the integer array.
  • n integers with neighboring elements separated by a space representing the elements of the array.

Output

One line containing n integers which are the sorted array in ascending order, also separated by spaces.

Example

Input:

5

2 0 -3 4 5

Output:

-3 0 2 4 5

Solution: C++

#include<iostream>

using namespace std;

// merge the two ordered arrays b and c into the original array a
void merge(int a[], int l, int m, int r){
    int n1 = m - l + 1; //size of array b
    int n2 =  r - m; //size of array c

    // create temp arrays of b and c
    int B[n1], C[n2];

    int i, j;
    // copy arrays a and b into temp arrays B and C
    for (i = 0; i < n1; i++)
        B[i] = a[l + i];
    for (j = 0; j < n2; j++)
        C[j] = a[m + 1 + j];

    // merge the temp arrays A and B back into array a in the right position
    i = 0; // index of B
    j = 0; // index of C
    int idx = l; // index of the array a
    while (i < n1 && j < n2){
        if (B[i] <= C[j]){
            a[idx] = B[i];
            i++;
        }
        else{
            a[idx] = C[j];
            j++;
        }
        idx++;
    }

    // copy the remaining elements of B into a
    while (i < n1) {
        a[idx] = B[i];
        i++;
        idx++;
    }

    // copy the remaining elements of C into a
    while (j < n2) {
        a[idx] = C[j];
        j++;
        idx++;
    }
}

void mergeSort(int a[], int l, int r){
    if (l < r){
        int m = l+(r-l)/2; //index to split the the array a in two parts
        mergeSort(a, l, m); // sort the first part
        mergeSort(a, m+1, r); // sort the second part
        merge(a, l, m, r); //merge the ordered two sub-array into array a
    }
}

int main(){
    int size;
    cin>>size;
    int a[size];
    for(int i=0; i<size; i++)
        cin>>a[i];

    mergeSort(a, 0, size - 1);

    for (int i=0; i < size; i++)
        cout<<a[i]<<" ";
}

Related posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s