ソートアルゴリズム

heap_sort.js

let parent = i => Math.floor(i - 1);
let left = i => (i + 1) * 2 - 1;
let right = i => (i + 1) * 2;
let swap = function (items, i, j) {
    let temp_i = items[i];
    items[i] = items[j];
    items[j] = temp_i;
};

let get_largest_node = function (items, i,  heap_size) {
    let l = left(i);
    let r = right(i);
    
    let larger = (l < heap_size && items[l] > items[i]) ? l : i;
    return (r < heap_size && items[r] > items[larger]) ? r : larger;
}

let max_heapify = function (items, i, heap_size) {
    let largest = get_largest_node(items, i, heap_size);
    if (largest !== i) {
        swap(items, i, largest);
        max_heapify(items, largest, heap_size);
    }
};

let build_max_heap = function (items) {
    for (let i = Math.floor(items.length / 2) - 1; i >= 0; i--) {
        max_heapify(items, i, items.length);
    }
}

let heap_sort = function (items) {
    build_max_heap(items);
    for (let i = items.length - 1; i > 0; i--) {
        swap(items, 0, i);
        max_heapify(items, 0, i);
    }
}

var items = [5, 2, 4, 6, 1, 8];
heap_sort(items);
console.log(items);

merge_sort.js

var merge = function (items, left, center, right) {
    var leftItems = [];
    var rightItems = [];

    for (var i = 0; i < (center - left + 1); i++)
        leftItems[i] = items[left + i];

    for (var i = 0; i < (right - center); i++)
        rightItems[i] = items[center + i + 1];

    var l = 0;
    var r = 0;
    for (var i = left; i <= right; i++) {
        if (r === rightItems.length || l < leftItems.length && leftItems[l] < rightItems[r]) {
            items[i] = leftItems[l];
            l++;
        } else {
            items[i] = rightItems[r];
            r++;
        }
    }
};

var merge_sort = function (items, left, right) {
    if (left < right) {
        // / 2
        var center = Math.floor((left + right) / 2);
        merge_sort(items, left, center);
        merge_sort(items, center + 1, right);
        merge(items, left, center, right);
    }
};

var items = [5, 2, 4, 6, 1, 8];
merge_sort(items, 0, items.length - 1);
console.log(items);