function insertionSort(arr) {
    const len = arr.length;
    if (len <= 1) return 0;

    const mid = Math.floor(len / 2);
    const arrL = arr.slice(0, mid);
    const arrR = arr.slice(mid);
    let ret = insertionSort(arrL) + insertionSort(arrR);

    let i = 0;
    let l = 0;
    let r = 0;
    while (l < arrL.length && r < arrR.length) {
        if (arrL[l] <= arrR[r]) {
            arr[i++] = arrL[l++];
        } else {
            arr[i++] = arrR[r++];
            ret += mid - l;
        }
    }
    while (l < arrL.length) {
        arr[i++] = arrL[l++];
    }
    while (r < arrR.length) {
        arr[i++] = arrR[r++];
    }
    return ret;
}