merge-sort-inplace.js is not In Place

Author: forrest-akinCreated Nov 29, 2016Updated Nov 29, 2016

merge-sort-inplace.js is not an example of an in place Merge Sort because arrays are being created and concatenated. Here's an example of an in place merge sort...

javascript
const mergeSort = (array, left = 0, right = array.length - 1) => {
    
    if (left >= right) return array

    let mid = Math.floor((left + right) / 2),
        i = mid + 1
    
    mergeSort(array, left, mid)
    mergeSort(array, i, right)

    while (left <= mid && i <= right) {
        if (array[left] < array[i]) left++
        else {
            array.splice(left, 0, array.splice(i, 1)[0])
            left++
            mid++
            i++
        }
    }

    return array
}

Source: humanwhocodes/computer-science-in-javascript