5 ms·
I recently found a fun linear-time systolic sorting algorithm. I'd describe the serial implementation as unconventionally obvious. It's like insertion sort, w
by boothby 5y ago
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.
def index_sort(a):
n = len(a)
output = [None] * n
for i in range(n): #can run in parallel, damn the GIL
index = 0
for j in range(n):
if a[j] < a[i]:
index += 1
elif a[j] == a[i] and j < i:
index += 1
output[index] = a[i]
return output
- Snild 5y ago> linear-time But... there are two nested `range(n)` for loops. Typo?
- boothby 5y agoThat'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.