News for hackers. Stuff that matters.
Re:Unconventional Sorting Algorithms by boothby on Thursday October 21, 2021 @03:06PM (#28949429)
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.

There are no comments on this comment yet.