/**
 * @mergesort.cpp
 * @author Shirish Reddy <shirishreddy89@gmail.com>
 * 
 * Merge sort sorts the elements of array in place, complexity O(nlogn)
 * 
 */ 


#include <iostream>
#include <limits>

using namespace std;

/** 
 * Merge function merges and sorts (elements) two arrays 
 * 
 * @param Array whose elements are to be merged
 * @param Indices of the portions of array to be sorted and merged
 * @return Doesnot return any value, as the elements are rearranged in place
 */
void merge(int *a, int p, int q, int r)
{

	int n1 = q-p+1;
	int n2 = r-q;
	
	int *L = new int[n1+1];
	int *R = new int[n2+1];
	
	for(int i=0; i<n1; i++)
		L[i] = a[p+i];
	for(int j=0; j<n2; j++)
		R[j] = a[q+j+1];
	L[n1] = 999;
	R[n2] = 999;
	int i=0; int j=0;
	
	for(int k=p; k<=r; k++){
		if(L[i] <= R[j]) {
			a[k] = L[i];
			i++;
		}
		else if(L[i] >= R[j]) {
			a[k] = R[j];
			j++;
		}
	}
}

/**
 * The recursive function of mergesort which splits the array in to two halves. 
 * 
 * The function after splitting the array in the lowest possible split size, i.e when only single element is present
 * it moves in bottom up approach, Calls the function merge which sorts and merges the sub-problems
 *
 * @param Array to be split and sorted
 * @param Index of first and last elements of array
 * @return No return value
 */	
void merge_sort(int *a, int p, int r)
{
	int q;
	if(p<r) {
		q = (p+r)/2;
		merge_sort(a, p, q);
		merge_sort(a, q+1, r);
		merge(a, p, q, r);
	}
}

int main(){
	int A[] = {1,5,4,3,8,7,5,3,2,6,5};
	merge_sort(A, 0, 10);
	for(int i=0; i<=9; i++){
		cout<<A[i]<<endl;
	}
	return 0;
}
			

1
2
3
3
4
5
5
5
6
7