【アルゴリズム(JS実装)】Merge Sort - 医学生わくばの欲張り技術ブログ

　どうも、わくばです！

　今日はJDLA認定講座の最後の試験でした。無事合格しましたので、これでやっとE資格試験を受験できます。

　なんでこんなにめんどくさいのだ（笑）

　機械学習は統計的な処理もしっかり含まれていて、医学でも役立つので何れにせよ頑張りきろうと思います。

　さて今日のアルゴリズムですが、Merge Sortです。いくつかアルゴリズムをコードに起こしてきましたが、アルゴリズムのぱっと見の印象では意外と複雑さの検討がつきにくいですね。　

　ソート系は難易度低い印象ですがBubble Sortや今回のMerge Sortなど、所見でコードを書こうとするとなかなかしんどいです（笑）

　Merge Sortはこんな感じになりました。

const mergeSort = array => {

    const merge = (left, right ) => {
        //分割した左のインデックス
        let i = 0;
        //分割した右のインデックス
        let j = 0;
        const result = [];
        while (i < left.length && j < right.length) {
            //左と右で小さい方をresultに追加
            if(left[i]< right[j]){
                result.push(left[i]);
                i++;
            }else{
                result.push(right[j]);
                j++;
            } 
        }
        //残ったものをくっつける
        return result.concat(i < left.length ? left.slice(i) : right.slice(j));
    }

    if (array.length > 1) { 
        const { length } = array;
        const middle = Math.floor(length / 2);
        //分割後ひたすら再帰的に繰り返す
        const left = mergeSort(array.slice(0, middle )); 
        const right = mergeSort(array.slice(middle, length)); 
        //最後にくっつける
        array = merge(left, right ); 
    }
    return array; 
}
 
let arr = [5,4,3,7,6,5,1,8,7,6,9,33,5,7,89]
console.log(mergeSort(arr))

>>>[
    1,  3,  4, 5, 5, 5,
    6,  6,  7, 7, 7, 8,
    9, 33, 89
    ]