1
$\begingroup$

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.)

|cite|improve this question
$\endgroup$
  • $\begingroup$ Here are the typos on the pseudocode. a) tmp.element > current_element should be tmp.key > current_element. b) last_element is not updated. $\endgroup$ – John L. Jul 5 '19 at 4:23
  • 1
    $\begingroup$ Wikipedia is supposed to be a reference. Why would you even think of putting something you just made up there? $\endgroup$ – Raphael♦ Jul 5 '19 at 6:22
  • $\begingroup$ (You might want to present that pseudo code on CodeReview.) $\endgroup$ – greybeard Jul 5 '19 at 6:29
  • $\begingroup$ @greybeard Already did. $\endgroup$ – coderodde Jul 10 '19 at 8:54
  • $\begingroup$ I literally meant your pseudo-code - not that I remembered your presentation of a sequential Java implementation $\endgroup$ – greybeard Jul 10 '19 at 17:33
4
+250
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ illuminative re. cohesion $\endgroup$ – greybeard Jul 5 '19 at 6:31
1
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I have to disagree on the 3rd paragraph of your answer: suppose the sorting key is a class with satellite data that does not impact the sorting by itself. Counting will lose some information, in such a case. For example, we are sorting persons by first name with two Jacks in the input array (one Doe, another Johnson). We cannot simply save any of them behind the counter; we will lose some of them. $\endgroup$ – coderodde Jun 24 '19 at 17:04
  • $\begingroup$ Also note that the space complexity is Theta(k), where k is the number of distinct numbers. Thus, the running time is O(nk). $\endgroup$ – coderodde Jun 29 '19 at 9:23
  • $\begingroup$ You replaced repeated items with item+counter. This change is independent on the rest and may be applied to original insertion sort, as well as your sort may be implemented without this detail. $\endgroup$ – Bulat Jun 29 '19 at 10:44
  • 2
    $\begingroup$ You may look into algorithm books, I especially recommend Sedgewick ones. You will find there a lot of variations on basic algorithms which don't deserve carrying their own names. $\endgroup$ – Bulat Jun 29 '19 at 10:51
  • 1
    $\begingroup$ I don't mean that it's mentioned there. Actually he mainly looks into variations of quick and merge sorts since these are the most useful ones. What I say is that there are dozens of variations we can make into each sorting algorithm, so in most cases they don't get indivisdual names. Exceptions are algorithms like timsort that became popular. $\endgroup$ – Bulat Jun 29 '19 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.