News for hackers. Stuff that matters.
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.

  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
Re:Unconventional Sorting Algorithms by Snild on Thursday October 21, 2021 @02:14PM (#28948672)
> linear-time

But... there are two nested `range(n)` for loops. Typo?

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.