Hacker News Reader

I think the second solution from SO is almost the same as yours, including having begun with Golomb coding: http://preshing.com/20121026/1mb-sorting-explained

However, they explain that Golomb coding isn't quite enough for the 1M case and switch to arithmetic coding instead.

Ah seems I was a bit too optimistic with my estimation of the number of bits. Shame, that means a simple solution is pretty much impossible.

>The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756), but I've not seen a good writeup of an actual algorithm.

I reckon the easiest way to actually achieve that bound is to use the combinatoric number system. I've seen people refer to arithmetic encoding but I'm not too sure on the exact details, they're probably encoding the gaps between numbers but then there'll be some loss as those aren't IID, using the exponential distribution does seem to get you below the bound though, even if it is extremely annoying to implement.

For the combinatorial number system you basically need to sum (10^100 + 10^6 choose x + k) for all numbers x where k is the position of x in the (sorted) list. This would have been many times easier if you didn't need to take possible repeated values into account, but it is what it is.

If I'm honest both are complicated enough that I worry they'll be nigh impossible to implement without accidentally using 2MB of RAM.

Edit: Actually, just use Golomb-Rice codes for the gaps, if you pick the parameters right you'll need [d/128]+7 bits (rounded to the nearest integer) for a gap of size d, which is good enough. Since every gap uses a whole number of bits you'll just need to update and insert a few bits to update, rather than basically rewriting the whole thing (although you'll still need to shift the entire tail by a few bits).

>"I'm a fan of the actual (in-RAM, no tricks) problem and its variants."

This particular problem as stated on S.O. aside do you consider disk-based sorting one of the tricks? I would be curious to hear some of the other tricks as well as variants of this problem space.

I consider it not in-RAM.

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

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.

Interesting is this a counting sort then?

Might you or someone else have a link that states the whole interview question?

> 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.

Seconded, I googled bitfields and Stack Overflow and still don't understand the OP even a little.

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.

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...

> My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago.

Is it possible for you to share the code? Still don't quite get how that encoding related/helps in sorting the numbers.

Interesting, sort of bucket sort using a linked list if I understand correctly. How do you determine the optimal number of bits - 12 for 32bit and 6 for 1e8 = 30bit?

Why is the entropy of the sorted list smaller?

The entropy of a signal is the logarithm base 2 of the number of signals that you could possibly be trying to send. Because with perfect compression, that is how many bits you need to encode that many different signals.

Since not all lists are sorted, there are more lists of a given size than sorted lists.

1M (ordered) list of numbers < 10^8 requires 3.16MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits. Basically calculating number of different possible types of lists, taking its log is the entropy. Both the lists [1, 2] and [2, 1] are same if we don't want the ordering information. In the second case we just need counts of number with property that count[0] + count[1]+...+count[10^8] = 10^6 as counts give perfect information for the sorted list.

Because it's easier to compress (compared to when its contents is in a random order).