-
Notifications
You must be signed in to change notification settings - Fork 0
/
103-merge_sort.c
92 lines (86 loc) · 2.15 KB
/
103-merge_sort.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
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
89
90
91
92
#include "sort.h"
#include <stdlib.h>
/**
* merge_sort - sorts an array of integers in ascending order
* using the Merge sort algorithm
* @array: array of integers
* @size: size of array
*/
void merge_sort(int *array, size_t size)
{
int *tmp = NULL;
if (!array || size < 2)
return;
tmp = malloc(sizeof(int) * size);
if (!tmp)
return;
merge_sort_rec(array, tmp, 0, size - 1);
free(tmp);
}
/**
* merge_sort_rec - sorts an array of integers in ascending order
* using the Merge sort algorithm
* @array: array of integers
* @tmp: temporary array of integers
* @low: low index
* @high: high index
*/
void merge_sort_rec(int *array, int *tmp, int low, int high)
{
int mid = 0;
if (low < high)
{
mid = (low + high) / 2;
merge_sort_rec(array, tmp, low, mid);
merge_sort_rec(array, tmp, mid + 1, high);
merge(array, tmp, low, mid, high);
}
}
/**
* merge - merges two subarrays of integers
* @array: array of integers
* @tmp: temporary array of integers
* @low: low index
* @mid: middle index
* @high: high index
*/
void merge(int *array, int *tmp, int low, int mid, int high)
{
/*
* i tracks left subarray and j tracks right subarray.
* k tracks merged subarray. The logic of the merge
* subroutine is to use the temporary array to store
* the sorted elements of the left and right subarrays
* determined by the indices i and j.
*/
int i = 0, j = 0, k = 0;
printf("Merging...\n");
printf("[left]: ");
print_array(array + low, mid - low + 1);
printf("[right]: ");
print_array(array + mid + 1, high - mid);
/*
* interleave the elements of the left and right subarrays
* in sorted order into the temporary array using the two
* pointer algorithm.
*/
for (i = low, j = mid + 1, k = low; k <= high; k++)
{
if (i <= mid
&& (j > high /* first right subarray element not considered */
|| array[i] <= array[j]))
{
tmp[k] = array[i]; /* left subarray element is smaller */
i++;
}
else
{
tmp[k] = array[j]; /* right subarray element is smaller */
j++;
}
}
for (k = low; k <= high; k++) /* copy sorted elements to array */
array[k] = tmp[k];
printf("[Done]: ");
print_array(array + low, high - low + 1);
}