4 ms·
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 a
by mkingston 10y ago
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.
- openasocket 10y agoOK, 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...
- cousin_it 10y agoA 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.