-
merging
Say i have n vectors that are sorted. I can't think of a better algorithm to merge than searching the first of all n vectors to find minimum then pop that then continue. I think this would be too slow, but I can't think of anything more efficient.
Thanks
Michael
-
>I think this would be too slow
Why? Have you tried it, profiled the execution, and determined it to be too slow? Or are you just thinking about it and going "golly, this has a lot of steps"? There are two problems with the latter:
1) Programmers are notoriously bad at guessing where bottlenecks lie.
2) Algorithms are notoriously good at looking slow but being zippy.
-
You could just do a sort by taking each element of every vector at a time in no particular order. This is probably what I'd do if the vectors weren't sorted. But since they are, your idea sounds pretty good.
-
When you have more than 2 sorted vectors to merge, an excellent way to handle the merging is to reference each vector in a heap. Whether that means that your heap stores pointers to the vectors, or indexes to those vectors within the array of those vectors is up to you.
You always extract an item from the vector that is at the head of the heap. Then you downheap (or is it upheap, I get mixed up), and repeat
That's the way to do external mergesort.
-
I like the heap idea. I get upheap and downheap confused too don't worry lol. but I'm not sure if I shouldn't just take Prelude's advice. Eh I'll code both. Thanks for the advice. I greatly appreciate it!