I have an array of objects. the objects have a Boolean value in them that I want to use as a key for sorting the array (all objects with true come before all objects with false) but otherwise leave things in the same order.
Is there a simple, in-place, O(n) solution to this? Maybe some variant of radix-sort?
See here for a discussion on this topic. You can basically have either an O(n)-solution which needs additional space or a O(n log n) in-place solution.
Merge sort. O(n log n).
Hmm. With a linked list it should be feasible - you'd search for the first "false" entry and keep it as the "insertion location". (If there are no "false" entries then you're done anyway :) Then just iterate through the whole list - if you're before the insertion location and find a "false" entry or if you're after the insertion location and find a "true" entry then move it to directly before the "insertion location". So far, so O(n).
Now you can convert an array into a linked list in O(n) and you can copy the data back into the array in O(n). So I think it would work in terms of complexity - but it's not in-place. I'll think about whether it can be done in-place...
