hmph. for some reason, I'm not getting the code formatting. There's lots of extraneous code in here, but it's something you can copy/paste into an IDE and start tinkering with.
I was thinking if they were sorted, there would be a single-pass way to do it. But since they're not, this will do.
The output of the above, with my implementation, is:
The final output is not in the form of a Vector, but you could either post-process it into one, or use a Vector to start with, and instead of a key-value "mapping" in the HashMap, you can use the index of the merge vector itself (when adding to it, you'd be using the add method that inserts into a specified index). This implies then, you'd do *pre* processing, to determine how large your merge vector should be made. [ December 09, 2008: Message edited by: Mike Curwen ]