Yuan's blog

刘沛源的博客

0%

归并排序

发表于 更新于 Disqus：
本文字数： 390 阅读时长 ≈ 1 分钟

归并排序代码

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
// divide_merge.c

#include <stddef.h>
#include <stdio.h>
#include <limits.h>

void merge(int *arr, size_t p, size_t q, size_t r) 
{
        size_t n1 = q - p + 1;
        size_t n2 = r - q;

        int arr_left[n1+1], arr_right[n2+1];
        for (int ind = 0; ind < n1; ind++) {
                arr_left[ind] = arr[p + ind];
        } 
        for (int ind = 0; ind < n2; ind++) {
                arr_right[ind] = arr[q + 1 + ind];
        } 
        // sentinel
        arr_left[n1] = arr_right[n2] = INT_MAX;

        int ind = 0;
        int jnd = 0;
        
        for (int knd = p; knd <= r; knd++) {
                if (arr_left[ind] <= arr_right[jnd]) {
                        arr[knd] = arr_left[ind];
                        ++ind;
                } else {
                        arr[knd] = arr_right[jnd];
                        ++jnd;
                }
        }
}

void merge_sort(int *arr, int head, int tail)
{
        if (head < tail) {
                int mid = (head + tail) / 2;
                merge_sort(arr, head, mid);
                merge_sort(arr, mid + 1, tail);
                merge(arr, head, mid, tail);
        }
}

void divide_merge_sort(int *arr, size_t arrsiz)
{
        merge_sort(arr, 0, (int)arrsiz - 1);
}

效率测试框架

与 插入排序 类似

测试结果

直接起飞！！！

>>> DEVIDE-MERGE SORT >>>
[SORT array_size=10]
    gen_time: 0
        ORIGION ARRAY: [ 3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
    sort_time: 0
        SORTED ARRAY: [ 1, 2, 3, 3, 5, 5, 6, 6, 7, 9]
[SORT array_size=100]
    gen_time: 0
    sort_time: 0
[SORT array_size=10000]
    gen_time: 0
    sort_time: 0
[SORT array_size=100000]
    gen_time: 0
    sort_time: 0
[SORT array_size=1000000]
    gen_time: 0
    sort_time: 0
<<< DEVIDE-MERGE SORT <<<