Merge Sort

Algorithm , , コメント 
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
#ifndef ALGORITHM_MERGE_SORT_H
#define ALGORITHM_MERGE_SORT_H
/* マージソート */
void merge_sort (int array[], int left, int right) {
    int i, j, k, mid,l;
    int work[10];  // 作業用配列
    if (left < right) {
        mid = (left + right)/2; // 真ん中のIndex
        merge_sort(array, left, mid);  // 再帰関数による左を整列
        merge_sort(array, mid+1, right);  // 再帰関数による右を整列

        for (i = mid; i >= left; i--) {// 左半分
            work[i] = array[i];
        }
        for (j = mid+1; j <= right; j++) {
            work[right-(j-(mid+1))] = array[j]; // 右半分を逆順
        }


        i = left; j = right;
        for (k = left; k <= right; k++) {
            if (work[i] < work[j]) {
                array[k] = work[i++];
            }else{
                array[k] = work[j--];
            }
        }

        for (l = 0; l <= right; l++) {
            printf("%d ", work[l]);
            if(l==mid){
                printf("| ");
            }
        }
        printf("\n");
    }
//    printf("step %2d:  ",k);
//    print_array(array,10);
}
#endif //ALGORITHM_MERGE_SORT_H