[Algorithm] Merge sort – Merge Sort

March 4, 2015 nguyenvanquan7826 Algorithm 5 responses

Merge sort algorithm (Merge Sort) is one of the sorting algorithm or used. Nearly identical to Quick sort algorithm (Quick Sort) an arrangement by splitting the original array 2 half, but with Quick Sort element is used as a landmark comparison between Merge Sort is still clearly divided into, then sort each array “blend” 2 array rearranged.

Here is the C language code of the algorithm:

01
02
03
04
05
06
07
08
09
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
#include <stdio.h>
 
/* xuat mang a tu vi tri l (left) den vi tri r (right)*/
void xuat(int a[], int l, int r) {
    int i;
    for (i = l; i <= r; i++){
        printf("%d \t", a[i]);
    }
    printf("\n");
}
 
/* tron 2 mang
 * mang a[l -> m] da sap xep
 * mang a[m+1 -> r] da sap xep
 * */
void tron(int a[], int l, int m, int r){
    int i, length;
    int l_end = m - 1;
    i = l;
    length = r - l;
     
    int temp[length];
     
    /* tron cac phan tu cua 2 mang con cua a*/
    while(l <= l_end && m <= r) {
        if (a[l] <= a[m]) {
            temp[i++] = a[l++];
        } else {
            temp[i++] = a[m++];
        }
    }
     
    /* Neu mang dau tien chua het */
    while(l <= l_end) {
        temp[i++] = a[l++];
    }
     
    /* Neu mang thu 2 chua het*/
    while(m <= r) {
        temp[i++] = a[m++];
    }
     
    for (i = 0; i <= length; i++, r--) {
        a[r] = temp[r];
    }
}
 
/* thuat toan sap xep tron*/
void sx_tron(int a[], int l, int r) {
    //xuat(a, l, r);
    int m;
    if(l < r) {
        m = (l + r) / 2;
        sx_tron(a, l, m);
        sx_tron(a, m + 1, r);
        tron(a, l, m + 1, r);
    }
}
 
int main(){
    int n = 5;
    int a[] = {2, 6, 3, 8, 5};
    sx_tron(a, 0, n-1);
     
    xuat(a, 0, n - 1);
    return 0;
}