Re:Unconventional Sorting Algorithms
by boothby on Thursday October 21, 2021 @01:35PM
(#28948014)
I recently found a fun linear-time systolic sorting algorithm. I'd describe the serial implementation as unconventionally obvious. It's like insertion sort, without all the bother of swapping.
[ Parent
| on HN ]
> linear-time
But... there are two nested `range(n)` for loops. Typo?
That's the serial implementation, which is clearly O(n^2). The systolic algorithm runs in linear time on specialty hardware (similar to a tensor core, which can do comparisons in a square matrix, and can perform row-sums). Or, if we ignore communication overheads, it can run in O(n) time with O(n) parallel workers.