merge sort

アルゴリズム

1. 数列を半分半分に分割していって並び替えたものを作る
2. 順番を揃えつつmergeする

基本はこれだけ。最小分割単位１では何もしないこととmergeするときのアルゴリズムに注意する。

コード例

startはsortするはじめのindexで,endは最後のindex+1に対応していることに注意してください。

#include<iostream>
using namespace std;

void merge(int array[], int temp[], int start, int middle, int end){
    int i;
    //今の並びをcopyしておく
    for(i=start; i<end; i++){
        temp[i] = array[i];
    }
    int left = start;
    int right = middle;
    int current = start;
    while((left<middle)&(right<end)){
        if(temp[left]<=temp[right]){
            array[current] = temp[left];
            left++;
        }else{
            array[current] = temp[right];
            right++;
        }
        current++;
    }
    // leftの要素が残っていたら後ろに追加
    if(middle-left>0){
        for(i=left; i<middle; i++){
            array[current] = temp[i];
            current++;
        }
    }
}

void merge_sort(int array[], int temp[], int start, int end){
    //分割してmerge_sortされたものをmergeする
    int middle;
    middle = (start+end)/2;
    if(start+1<end){
        merge_sort(array, temp, start, middle);
        merge_sort(array, temp, middle, end);
        merge(array, temp, start, middle, end);
    }
}

void mergeSort(int N, int array[]){
    int temp[N] = {};
    merge_sort(array, temp, 0, N);
}

int main(void){
    int i;
    int N = 10;
    int array[N] = {1,3,5,2,4,7,8,10};
    for(i=0; i<N; i++){
        cout << array[i] << " ";
    }
    cout << endl;
    mergeSort(N, array);
    for(i=0; i<N; i++){
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}