5 ms·

I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.

mikepurvis 7y ago
The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.
- bogomipz 7y ago
  Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?
  - Noumenon72 7y ago
    Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.
    - efreak 7y ago
      For sorting 3,5,8,2,7: you take 0000000000, representing all 10 single digit numbers (0-9), and encode the given numbers into it as 0011010110. Now you just read out each one in order: 2,3,5,7,8. No need to store the actual numbers themselves. It's possible that I'm getting this wrong, but this is my understanding of it.
  - mikepurvis 7y ago
    The original Pearls page seems to have been taken down, but the web archive remembers it: http://web.archive.org/web/20071012005100/http://www.cs.bell-labs.com/cm/cs/pearls/cto.html http://web.archive.org/web/20071012005100/http://www.cs.bell...
  - dntbnmpls 7y ago
    > 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.

mikepurvis 7y ago

The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.

bogomipz 7y ago
Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?
- Noumenon72 7y ago
  Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.
  - efreak 7y ago
    For sorting 3,5,8,2,7: you take 0000000000, representing all 10 single digit numbers (0-9), and encode the given numbers into it as 0011010110. Now you just read out each one in order: 2,3,5,7,8. No need to store the actual numbers themselves. It's possible that I'm getting this wrong, but this is my understanding of it.
- mikepurvis 7y ago
  The original Pearls page seems to have been taken down, but the web archive remembers it: http://web.archive.org/web/20071012005100/http://www.cs.bell-labs.com/cm/cs/pearls/cto.html http://web.archive.org/web/20071012005100/http://www.cs.bell...
- dntbnmpls 7y ago
  > 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.