4 ms·
Another possible implementation which is log^2(n) https://en.wikipedia.org/wiki/Bitonic_sorter https://en.wikipedia.org/wiki/Bitonic_sorter
by en4bz 9y ago
Another possible implementation which is log^2(n) https://en.wikipedia.org/wiki/Bitonic_sorter https://en.wikipedia.org/wiki/Bitonic_sorter
- monochromatic 9y agoNo, you can’t even read the whole array in O(log^2(n)). It’s not possible to do better than O(n) without “cheating.”
- IAmLiterallyAB 9y agoI think the trick is you can run it in parallel. Which under ideal circumstances may give that kind of performance. But this is the first I've heard of this algorithm.