What is the name of this sorting algorithm?

Question

I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays.

Basically, it marches through the input array and for each new array component it inserts it into a sorted doubly-linked list. It has two optimizations:

1. each list node has a count; instead of adding a new node with the same key, existing node is reused by incrementing its counter,
2. the sort maintains a reference to the most recently accessed list node. This allows faster search for the next list node in case the two relevant keys are "close" to each other.

My question is: what is the name of that sort? (I believe I am not the first one to conceive it.)

Answer 1

What is the name of that sort?

There is no existing name for it, I would believe.

If I had to name it, its name could be "caching and counting insertion sort". Here are the considerations.

• It is a kind of insertion sort since it maintains a single ordered linked-list all the way by inserting elements one by one into that ordered linked-list.
• "Caching" and "counting" are the basic two features of that insertion sort. Caching tries to make it faster to find the right location to insert by taking advantage of possible locality coherence. Counting is a common strategy to deal with the situation when duplicates happen often. Both caching and counting are standard terms that are easily recognizable.
• It happens that both words start with "c", which is helpful for reading and memorizing.
• "caching" is put before "counting" since "caching" is a more distinguishing feature of the algorithm. It is better to make the name less similar to the existing counting sort.
• This is not a very cohesive name, since there is no strong coupling between the two techniques used in that sort. The technique of caching could be applied to almost all kinds of sort. The technique of counting could be applied to almost all kinds of sort as well independently. The only meaningful connection between them is that if this caching technique improves the speed a lot, it is more likely that there are lots of duplicates, then the counting technique might be even more useful.
• "Caching and counting insertion sort" or "caching-counting insertion sort" is, in fact, more like a description instead of a proper name.

I would not recommend a name like "curve sort" unless you can show me some direct or obvious connection between "curve" and that sort.

Should we name that sort?

Is that sort distinctive and cohesive enough to deserve a distinctive short name?

The combination of caching and counting might be distinctive enough. However, those two optimizations are not cohesive. In fact, it is reasonable to see the two as independent. Caching deals with locality while counting deals with duplicates. Each one of them can be removed or applied without affecting the other's usefulness or functionality. It is preferable to study either one of them separately. It is not preferred to give a name to a simple combination of two abstract features.

As said by Bulat, there could be dozens of variations we can make to each of the algorithms listed on this page or this Wikipedia article. In particular, the counting technique can be applied to most if not all of them. In most cases the variations don't get individual names. To be clear, not every variation get individual names that have become established or standardized. Of course, if you write an article to expound that sort, you can certainly give it a fancy cool name such as "curve sort" or "Rodionsort".

What else could be done?

In fact, it looks like more interesting to name a simplified version of your algorithm that does not use the counting technique "caching insertion sort" or simply "caching sort", since caching makes sense mostly with insertion sort.

There have been many discussions/articles about whether or how much certain sorting algorithms are cache-friendly. However, I have not seen a simple sorting algorithm that takes an explicit separate step in order to take advantage of the "smoothness" of the data, although it might be a simple step. The most similar step I have seen is the checking whether the given data have been sorted before or during sorting. Some complex sorting algorithms such as Timsort search for ascending or descending subarrays during sorting, which also use many other techniques. A simple algorithm called "caching sort" sounds attractive and pedagogical to me.

A slight generalization could be caching two elements instead of just one element. When a new element comes along, we could start searching the position for the new element from the cached element that is nearer to the new element. Then the sorting would be efficient for data stream that comes from two "smooth" sources that are mixed irregularly.

A further generalization could be caching even more elements with more involved caching policy. Or even layers of caches. Let me stop my brainstorming here.

Answer 2

Basically, it's insertion sort, but implemented in very unusual way - with O(n) extra memory, O(n) search for best place instead of O(n) moving elements around, extra per-node counter, and pointer to last element.

I personally find it interesting for moderate-sized arrays with groups of close values, but overhead of list maintenance may kill the performance compared to qsort.

And it's applicable to any values (not only numbers).