I must be missing something, because problem 2 seems easy. It's just an array of boolean values, right? So you just pass over the array once, counting the number of zeroes. Then pass of the first n elements (for n the number of zeroes) and write zero to them, and write one to all the rest of the array. That's clearly stable (right?), requires only two passes over the array so it's O(N) time, and the only memory used is an index for looping and the count of the number of zeroes so it's O(1) memory. I'm guessing I'm missing something important, what is it?
Suppose you have a type A ('0' in the original description) and a type B ('1' in the original description). Suppose any instance of A < any instance of B, but any given instance of A is not necessarily even comparable to another instance of A. Similarly any instance of B is not necessarily comparable to another instance of B. Now stably sort an array containing instances of A and B.
OK, now I see why this is hard, thanks. Now I'm gonna spend the next few days mulling over this problem :)
I noticed the problem is relatively easy if you're dealing with a linked list instead of an array, because you can easily move elements around. If there's some way to amortize that in the array case...
A linked list has O(n) extra space to play with, compared to an array, so of course everything is easier. You can't transfer algorithms from one to the other.
