# Name for this sorting algorithm

I’ve just been playing around with some numbers and stumbled across this sorting algorithm: Take a set of integers $$\{2,2,5,1,1\}$$. Count how many numbers you can subtract 1 from (without going negative) - (5)

Same for subtracting 2 - (3)

Same for subtracting 3 - (1)

Same for subtracting 4 - (1)

Finally for subtracting 5 - (1)

This creates a new ordered set $$\{5,3,1,1,1\}$$ Perform the exact same algorithm with this new set of numbers and it will produce $$\{5,2,2,1,1\}$$ which is the original set in descending order.

I’m fairly confident the time complexity is $$O(n^2)$$ (for inputs that are integers smaller than the set size). I can draw a diagram confirming that it works too. Just wondering if it already has a name? Thanks in advance

• In a broader sense, this is reminiscent of inverting a Ferrer's diagram, to give at least something to Google on. But I've never heard of sorting based on inverting the diagram twice. Fun idea! – Matthew Daly Jan 11 at 11:27
• @Matthew Daly that’s the diagram I created too. – Ben Crossley Jan 11 at 11:31
• The first step looks like the Layer Cake Representation. It also looks like you’re taking the conjugate Ferrer’s diagram in the second step. I don’t know a name for this algorithm, however. – Michael Burr Jan 11 at 11:48
• You can go from the second list to the final list in O(n) time, using the fact that the second list is already in descending order. – Alex Meiburg Jan 11 at 20:05
• So, my guess is, when there lots of repeating small inputs is really fast. Which makes it quite cool +1 – miraunpajaro Jan 11 at 22:49