Has anyone heard of a HART Sort?
I came across it in an old article about benchmarks on the PDP-11. Page 39. I had never heard of it though, and my Google-fu turns up ambulances.
New for me too, but it looks like a good one:
Edit: I see it was included in the benchmarks for integer sorting but excluded for string sorting:
No benchmark for the Hart algorithm is included in this section. The complexity of the algorithm and the large amount of memory space it requires make this algorithm not suited to sort string fields.
I suppose it might be by
Hart co-authored 20 papers, among them the initial exposition of the A* search algorithm and the variant of the Hough transform now widely used in computer vision
1 Like
Ah, I see the code is later on in the article, with the comment
Besides an auxiliary pushdown stack, Hart uses an array SORT.ARRAY2 of “links” which point to items in SORT.ARRAY1 . Using an implicit balanced binary tree, Hart’s algorithm sorts by doing a minimal number of comparisons . Hart includes the pushdown at the end of array SORT.ARRAY2.
Aha, Richard Hart writes about the algorithm in Creative Computing, Volume 4 Number 1 “A New Fast Sorting Algorithm”
Also in Page 8 of this reprint of sorting and searching articles.
How to sort extremely fast with a minimum of comparisons, and a minimum of programming steps between comparisons.
…
This article starts with the theory described by Luther J. Woodrum in the IBM Systems Journal and describes an algorithm that not only uses a minimal number of comparisons, but also executes a minimal number of programming steps between each comparison.
Most excellent detective work! I like that it ends in the fab CC magazine.
1 Like
That’s very interesting - thanks for finding it.
I do wonder though - why is it not commonly known? (Or used). Or does it (now) go by another name?
I’ll have to try it and put it into my own sorting library, but it’ll have to wait a few days as I’m away from home and don’t have easy access to my usual “stuff” to test it with.
Cheers,
-Gordon