Insertion Sort Advanced Analysis

  • + 0 comments

    Idk why insertion sort that test on very large array or my skill issue. i was trying binany search on my insertion sort to improve speed, still timeout 4 tests. Im not sure i can use orther sort like merge sort or quick sort. so this is my code.

    const binary_search = (a: number[], r: number, n: number): number => {
        r = Math.max(0, Math.min(r, a.length - 1)) - 1
        let l = 0
        while (l <= r) {
            let m = Math.floor((l + r) / 2)
            if (n < a[m]) r = m - 1
            else l = m + 1
    
        }
        return l;
    }
    function insertionSort(a: number[]): number {
        let c = 0
    
        for (let i = 1; i < a.length; i++) {
            let x = a[i]
            let xi = binary_search(a, i, x)
    
            if (xi != i) {
                for (let j = i - 1; j >= xi; j--) { a[j + 1] = a[j]; c++ }
                a[xi] = x
            }
        }
    
        return c
    }