Merge Sort

Explanation:

picture

Code:

1
#include <stdio.h>
2
3
void mergeSubArrays(int array[], int idxL, int idxM, int idxR){
4
int i1, i2, idx;
5
int lenL = idxM - idxL + 1;
6
int lenR = idxR - idxM;
7
8
int L[lenL], R[lenR];
9
10
// copy array to arrayL and arrayR
11
for(i1 = 0; i1 < lenL; i1++){
12
L[i1] = array[idxL + i1];
13
}
14
for(i2 = 0; i2 < lenR; i2++){
15
R[i2] = array[idxM + i2 + 1];
16
}
17
18
19
i1 = 0;
20
i2 = 0;
21
idx = idxL;
22
while( i1 < lenL && i2 < lenR){
23
if(L[i1] < R[i2]){
24
array[idx] = L[i1];
25
i1++;
26
}else{
27
array[idx] = R[i2];
28
i2++;
29
}
30
idx++;
31
}
32
33
// put the lase elements to array
34
while(i1 < lenL){
35
array[idx] = L[i1];
36
idx++;
37
i1++;
38
}
39
while(i2 < lenR){
40
array[idx] = R[i2];
41
idx++;
42
i2++;
43
}
44
}
45
46
47
void mergeSort(int array[], int idxL, int idxR){
48
// seperate to sub arrays
49
if(idxL < idxR){
50
int m = idxL + (idxR - idxL) /2 ;
51
mergeSort(array, idxL, m);
52
mergeSort(array, m + 1, idxR);
53
54
mergeSubArrays(array, idxL, m, idxR);
55
}
56
}
57
Copied!

Test:

1
int main(){
2
int array[] = {3, 8, -5, 55, 1};
3
int len = sizeof(array) / sizeof(array[0]);
4
mergeSort(array, 0, len - 1);
5
6
for(int i = 0; i < len; i++){
7
printf("array[%d] = %d \n", i, array[i]);
8
}
9
return 0;
10
}
Copied!
Copy link