scandum / quadsort

Quadsort is a branchless stable adaptive mergesort faster than quicksort.
The Unlicense
2.13k stars 104 forks source link

[Question] Just trying to understand mysterious (for me) `else` #15

Closed MiloszKrajewski closed 2 years ago

MiloszKrajewski commented 2 years ago

Hi,

I'm trying to understand how some bits works, and I'm slightly puzzled by mysterious else:

In parity_swap_eight and parity_tail_swap_eight.

What adds to my confusion is the fact that I thought that I understood parity_swap_sixteen where after sorting 4 blocks x 4 items you check if it is a case when they are all "in row" so no need to merge anything.

I thought same thing happens in parity_swap_eight, but this else puzzles me.

Regards, Milosz

scandum commented 2 years ago

The else there is optional. What it does is that it only checks if the 8 elements are fully sorted if element 7 and 8 are sorted.

If elements 7 and 8 aren't sorted it's unlikely the rest is.

MiloszKrajewski commented 2 years ago

Thank you. Sorry for keeping this issue open for that long. At first I needed to digest it and ask some more questions and then I forgot. Thanks again!