// mergeSort :: [Numbers] -> [Numbers]
const mergeSort = array => {
    if (array.length <= 1) {
        return array;
    }
    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);
    
    return merge(mergeSort(left), mergeSort(right));
}

// merge :: ([Numbers], [Numbers]) -> [Numbers]
const merge = (left, right) => {
    const memory = [];
    let leftIdx = 0;
    let rightIdx = 0;
    
    while (leftIdx + rightIdx < left.length + right.length) {
        const leftElement = left[leftIdx];
        const rightElement = right[rightIdx];
        
        if (leftElement === null) {
            memory.push(rightElement);
            rightIdx++;
        } else if (rightElement === null) {
            memory.push(leftElement);
            leftIdx++;
        } else if (leftElement < rightElement) {
            memory.push(leftElement);
            leftIdx++;
        } else {
            memory.push(rightElement);
            rightIdx++;
        }
    }
    return memory;
}


let test = [9, 3, 1, 100, 200, 2, 10, 9];
let result = mergeSort(test)
result