Merge Sort

Search…
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!
​https://www.geeksforgeeks.org/merge-sort/​
Algorithm - Previous
Insertion Sort
Next - Algorithm
Count Prime
Last modified 3mo ago
Copy link
Contents
Explanation:
Code: