Merge Sort

MergeSort.cpp

// MergeSort.cpp : Defines the entry point for the console application.
// L.D.C.Lakmal

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <limits.h>

#define arrSize 6
using namespace std;

void mergeSort(int* arr, int p, int r);
void merge(int* arr, int p, int q, int r);
void printArray(int* arr, int inputSize);

void main(int argc, int argv[]){
	int arr[arrSize] = {50,10,40,60,30,20};
	cout << "Before Sorting... : ";
	printArray(arr, arrSize);
	mergeSort(arr, 0, 5);
	cout << "After Sorting... : ";
	printArray(arr, arrSize);
	system("PAUSE");
}

void mergeSort(int* arr, int p, int r){
	if(p<r){
		int q = (r+p)/2;
		mergeSort(arr, p, q);
		mergeSort(arr, q+1, r);
		merge(arr, p, q, r);
	}
}

void merge(int* arr, int p, int q, int r){
	int n1 = q-p+1;
	int n2 = r-q;

	int* L;
	L = new (nothrow) int[n1+1];
	int* R;
	R = new (nothrow) int[n2+1];

	for(int i=0; i<n1; i++){
		L[i] = arr[p+i];
	}

	for(int j=0; j<n2; j++){
		R[j] = arr[q+j+1];
	}

	L[n1] = INT_MAX;
	R[n2] = INT_MAX;

	int i = 0;
	int j = 0;

	for(int k=p; k<=r; k++){
		if(L[i] <= R[j]){
			arr[k] = L[i];
			i++;
		}else{
			arr[k] = R[j];
			j++;
		}
	}
	delete[] L;
	delete[] R;
}

void printArray(int* arr, int inputSize){
	for(int i=0; i<inputSize; i++){
		cout << arr[i] << " ";
	}
	cout << endl;
}