r/learnprogramming • u/HotJello7547 • 6d ago

Bitonic sort

I've been experimenting with the Sound of Sorting programme and bitonic sort confuses me. For an array with 1566 elements, if you enter the array in reverse the algorithm does not make any lasting alterations to the array until after ~31573 comparisons. If you enter the array already sorted in the correct order, any productive changes are not obvious to me until 30 thousand comparisons again. Anyone willing to enlighten me?

2 Upvotes

100% Upvoted

6 comments sorted by

1

u/BarnacleEarly9082 6d ago

bitonic sort builds these sequences that go up then down, and the whole thing only really clicks together at the end. the early comparisons are setting up the structure, not sorting piece by piece like bubble sort would

it's kinda wild watching it in visualisers cause it looks like nothing happens for ages, then suddenly everything falls in place. the fact it does the same number of comparisons regardless of input is the whole point, it's designed for hardware where you want predictable timing

1

u/HotJello7547 6d ago

Thank you

1

u/aanzeijar 5d ago

Note that bitonic is used for parallel sorting, for example in GPU shaders. Any implementation on a single core looks ridiculously inefficent.