> Interesting is this a counting sort then? Not really as all the input values are unique. So counting wouldn't do any good. It's basically using a bitfield l

> Interesting is this a counting sort then? Not really as all the input values are unique. So counting wouldn't do any good. It's basically using a bitfield long enough to encompass all possible values and then switching the bit of the input value. As an example, if you are dealing with 3 digit numbers, then the max possible value is 999 and the min possible is 0. So you need a bitfield that is 1000 bits long. And if your input values are 999, 2, 123 and 7. Then you set the 999th bit, 2nd bit, 123rd bit and the 7th bit. Now when you read the bitfield from the 0th bit to the 999th bit, you will find 4 set bits - the 2nd bit, the 7th bit, the 123rd bit and the 999th bit. So instead of viewing them as ordinal numbers but cardinal numbers, we get 2, 7, 123 and 999 which is sorted. Another way to view it is as setting the positions in an array. Instead of bits, lets say you have an array of 1000 ints all initialized to 0. Lets call this array MyBitArray. And if your input values are 999, 2, 123 and 7 then MyBitArray[999] = 1; MyBitArray[2] = 1; MyBitArray[123] = 1; MyBitArray[7] = 1; Now if you pass through the array in order and check for the indices with the value set to 1, you'll see that indexes 2, 7, 123 and 999 are set to 1 which incidentally gives you your sorted list. The difference between the array example and the bit example is that the bit example is much more space efficient. But the overall idea is the same.