OK, I am not familiar with the term adaptive sorting, but that looks like a slightly different issue from what I have in mind.
I am not talking about things that are already sorted, per se, but about treating repeated elements as a unit, and adding new instances of that repeated element to the unit once they are found.
For example, in a standard bubble sort (as before, I am using Bubble simply because it is easy to understand, not because it should be used in any real-world context to speak of), for a data set:
Code:
6, 6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
The first iteration would bubble up as
Code:
6, 6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 6, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 6, 2, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 6, 4, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 6, 1, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 6, 4, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 6, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 6, 8, 3, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 6, 3, 8, 12
^
6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 6, 3, 8, 12
^
Whereas for the 'muster sort' I posted, it would go:
Code:
6, 6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
6, 6, 4, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
4, 6, 6, 1, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
4, 1, 6, 6, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
4, 1, 6, 6, 6, 5, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
4, 1, 5, 6, 6, 6, 6, 1, 2, 4, 1, 4, 8, 3, 12
^
4, 1, 5, 1, 6, 6, 6, 6, 2, 4, 1, 4, 8, 3, 12
^
4, 1, 5, 1, 2, 6, 6, 6, 6, 4, 1, 4, 8, 3, 12
^
4, 1, 5, 1, 2, 4, 6, 6, 6, 6, 1, 4, 8, 3, 12
^
4, 1, 5, 1, 2, 4, 1, 6, 6, 6, 6, 4, 8, 3, 12
^
4, 1, 5, 1, 2, 4, 1, 4, 6, 6, 6, 6, 8, 3, 12
^
4, 1, 5, 1, 2, 4, 1, 4, 6, 6, 6, 6, 8, 3, 12
^
4, 1, 5, 1, 2, 4, 1, 4, 6, 6, 6, 6, 3, 8, 12
^
4, 1, 5, 1, 2, 4, 1, 4, 6, 6, 6, 6, 3, 8, 12
^
It is a specific sub-topic in adaptive sorting, I suppose, in that groups of successive items (where a 'column' of scalar items which have no lacunae) could be treatable as a unit. I may need to consider a further, properly adaptive variant of muster sort etc.