w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Why is Insertion sort using Binary search is slower than Insertion sort using Linear search?

Because the search and moving is combined in the first case and the search is just extra work in the second case.

Comparing integers is cheap, compared to moving integers around. Account for divisions, loop overhead, taken conditional jumps in every loop iteration vs. non-taken cond jumps, etc ...

PS. Indeed, in the linear search version, the inner loop is typical to look like:

.L5:
    leaq    -1(%rcx), %rsi
    movl    4(%rdi,%rsi,4), %eax
    cmpl    %eax, %r9d
    jge .L3
    movq    %rcx, %r8
    movq    %rsi, %rcx
    subl    $1, %edx
    movl    %eax, 4(%rdi,%r8,4)
    cmpl    $-1, %edx
    jne .L5
    movq    $-1, %rcx
.L3:

where the jge .L3 is executed only once and one can reasonably expect that branch to be predicted non-taken and not have a detrimental effect on the pipeline.

As for the inner loop in the other version, I don't want to look at it :)

PS. BTW, the linear search has also somewhat better locality, whereas the binary search jumps all over the place.





© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.