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

  • 3
    $\begingroup$ 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! $\endgroup$
    – user694818
    Commented Jan 11, 2020 at 11:27
  • $\begingroup$ @Matthew Daly that’s the diagram I created too. $\endgroup$ Commented Jan 11, 2020 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 11, 2020 at 11:48
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 11, 2020 at 20:05
  • 1
    $\begingroup$ So, my guess is, when there lots of repeating small inputs is really fast. Which makes it quite cool +1 $\endgroup$ Commented Jan 11, 2020 at 22:49

1 Answer 1


This algorithm is essentially counting sort


This algorithm can be computed in a single step when there is a diagonal symmetry in the Ferrer diagram

E.g permutations of 5,3,2,1,1

Or permutations of 4,3,2,1


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .