Algorithms/mergeSort.cpp at master · humayunk1/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/* This file contains a merge sort function
 * Code by: Humayun Kabir, humayun.k1@gmail.com */

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

//merge function -- merges two sorted arrays
void merge(int* & inArr, int lo, int mid, int hi, int* tempArr) {

	int i = lo, j = mid + 1;

	for(int k = lo; k <= hi; k++) {

		if( i > mid ) {
			tempArr[k] = inArr[j];
			j++;
		}
		else if( j > hi ) {
			tempArr[k] = inArr[i];
			i++;
		}
		else if( inArr[i] <= inArr[j] ) {
			tempArr[k] = inArr[i];
			i++;
		}
		else {
			tempArr[k] = inArr[j];
			j++;
		}
	}

	for(int k = lo; k <= hi; k++) {
		inArr[k] = tempArr[k];
	}

}

//mergeSort function
void mergeSort(int* & inArray, int lo, int hi, int* tempArr) {

	if(hi == lo)
		return;

	int mid = (lo + hi)/2;
	mergeSort(inArray, lo, mid, tempArr);
	mergeSort(inArray, mid + 1, hi, tempArr);

	//Merge the sorted arrays
	merge(inArray, lo, mid, hi, tempArr);
}

//This function sorts the input array inArr
void sort(int* & inArr, int length) {

	int *tempArr = new int[length];
	mergeSort(inArr, 0, length - 1, tempArr);

}


//Test the mergeSort function
int main() {

	int length = 10;
        int *arr = new int[length];

	srand( time(NULL) );

        cout<<"Input array: \n";
        for(int i = 0; i < length; i++) {
		//Generate a random number between 1 and 1000
                arr[i] = rand() % 1000 + 1;
                cout<<arr[i]<<" ";
	}

        cout<<"\n";

	sort(arr, length);

        cout<<"Sorted array: \n";
        for(int i = 0; i < length; i++)
                cout<<arr[i]<<" ";
        cout<<"\n";

	return 0;
}