2
$\begingroup$

I'm seeking information about a specific sorting algorithm. This algorithm performs pairwise comparisons and distinguishes between three states:

a > b: In this case, standard sorting logic proceeds (b precedes a).
a < b: As usual, a precedes b.
a = b: when elements are considered equal, both a and b are "fused" through some operation, resulting in a single element, denoted as c. This fused element c participates in subsequent comparisons as if it were the original a or b. (the list is left with one less element). The sorting order/size of c is the same as a or b.

My specific questions are:

Is there a recognized name or classification for this type of sorting algorithm?

Are there any known examples or applications of this algorithm in practice?

If not, where should I look. I have interest in something like sorting networks with fusion, or optimizing some known sorting algorithm for this purpose.

My main concern with existing sorting algorithms is their assumption of a constant number of elements. When the logic relies on previously sorted elements being larger/smaller than the compared element, removing elements during the process might invalidate previous comparisons.

$\endgroup$
6
  • $\begingroup$ Why have you used the terms "fused through some operation"? If the resulting $c$ behaves in the same way as $a$ or $b$, why not simply say that drop/ignore any one of $a$ or $b$? Also, could you please tell how your sorting states differs from the regular "comparison based sorting model"? $\endgroup$ Jan 31 at 11:38
  • $\begingroup$ @Inuyasha Yagami a, b, c could be pointers to some data that need merging when they have the same size. I used the word "fused", because I don't know the terminology for this particular algorithm. The sorting algorithms I know presume that the total number of elements remains constant, so they cannot be easily adapted when some elements may disappear. I guess, if the algorithm exists, that the removed element may be replaced with some infinite/null value, but that would invalidate assumptions about elements previously sorted. $\endgroup$
    – vakvakvak
    Jan 31 at 11:46
  • $\begingroup$ I am not sure there is a specific name for it. It looks like an optimization applicable to multiple algorithms, be that mergesort, quicksort, or some other. It also would result in $O(n'\log n' + n)$ time complexity, where $n'$ is the number of unique elements. $\endgroup$
    – rus9384
    Jan 31 at 13:04
  • $\begingroup$ Sorry, the time complexity would be $O(n\log n')$. $\endgroup$
    – rus9384
    Jan 31 at 13:54
  • $\begingroup$ Big-O must be unchanged because there is the case where all elements are different. With equal elements, you need little-o(n) or fewer different elements to get a smaller big-O for the sorting. $\endgroup$
    – gnasher729
    Jan 31 at 14:54

1 Answer 1

1
$\begingroup$

I think you can modify standard sorting algorithms to handle these goals.

One simple approach: whenever you find two elements $a,b$ with $a=b$, delete one of the two elements.

Another slightly more sophisticated approach: Construct a union-find data structure, where initially each element of the array is in its own set. Whenever you find two elements $a,b$ with $a=b$, call $\text{Union}(a,b)$ to merge those two set into a single set, and delete one of those two (whichever was not chosen as the representative for the union). Whenever you compare two elements, you are effectively comparing two sets by comparing their representatives.

How to delete an element: one approach is to sort them all, without deleting, then at the end remove all duplicates. Another approach have a separate bitmap of booleans, of the same length as the initial array, where each boolean is a flag that indicates whether that element has been deleted. To delete an element, set the flag to true. Periodically (say, once every $n$ steps), scan through the array and remove all items that are flagged for deletion. In some sorting algorithms, the deletion can be combined naturally with the work that's already being done: for instance, in QuickSort, the partition operation can naturally delete all items flagged for deletion, and in MergeSort, the merge operation can skip over all items flagged for deletion.

$\endgroup$
2
  • $\begingroup$ Do you mean, for example if pointers are being sorted, to keep both pointers in the array, but point them to the same object, to not invalidate the algorithm? The problem is that it doesn't drop repeated items, so it keeps processing redundant data. $\endgroup$
    – vakvakvak
    Feb 1 at 2:58
  • $\begingroup$ @vakvakvak, good point. See my edited answer for some ways to handle that. $\endgroup$
    – D.W.
    Feb 1 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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