-
Notifications
You must be signed in to change notification settings - Fork 0
/
mergeSort.c
49 lines (41 loc) · 1.01 KB
/
mergeSort.c
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
static void merge(int *left, int sizeLeft, int *right, int sizeRight, int *arr)
{
int i = 0, j = 0, k = 0;
while (i < sizeLeft && j < sizeRight)
{
if (left[i] < right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right[j];
j++;
}
k++;
}
/*Copy any remaining elements in the arrays*/
for (; i < sizeLeft; i++)
arr[k++] = left[i];
/*The below for loop is not required for mergeSortMain*/
// for (; j < sizeRight; j++)
// arr[k++] = right[j];
}
static void mergeSortMain(int *arr, int l, int h)
{
if (l >= h)
return;
int mid = (l + h) / 2;
mergeSortMain(arr, l, mid);
mergeSortMain(arr, mid + 1, h);
int tempSize = mid - l + 1;
int temp[tempSize];
for (int i = 0; i < tempSize; i++)
temp[i] = arr[l + i];
merge(temp, tempSize, arr + mid + 1, h - mid, arr + l);
}
void mergeSort(int *arr, int n)
{
mergeSortMain(arr, 0, n - 1);
}