mergesort

I'm familar with the standard recursive merge sort, but i'm trying to write an iterative version(breadth first), or what Knuth describes as "straight two-way merge". My problem lies in processing data sets which aren't values of 2^n. Anyone have any ideas? Should i just merge as many partitions of size K(current depth) as i can. then merge the list that doesn't fit onto the closest newly merged 2k size partition?

Is there a recursive mergesort? Mergesort is normally for lists that are too long to do in memory. Somehow I can't see this being recursive but that's just me.

In the real world, you can't always get sets that are 2^n. I think it is as you said: just merge it with the closest newly merged partition.

As a matter of interest, do you do the mergesort with 4 files or 3 files?

There is an algorithm described in Wirth's Data Structures + Algorithms = Programs but I don't know if it is the type you are using. It may be a mergesort, it may be polyphase. I'll have to dig the book out from my attic to find out.

I'm not mergeing files, I'm trying to use it to sort vectors.

the idea of the recursive merge is simple....

MergeSort{


conditional: if list size is 1 return;
else:
divide list in half. picking either ceiling or floor if its odd;
MergeSort on one half;
MergeSort on other half;
merge;

}

idea is with a list....(i hope it keeps my formatinng

7 8 9 5 9 3 45 9 8 6 45 2

7 8 9 5 9 3 45 9 8 6 45 2

7 8 9 5 9 3 45 9 8 6 45 2
.
. 45 9 8 6 45 2
.
45 9 8 6 45 2

then the idea is trace back up the tree merging and sortng.
the none recursive merge sort wants to start at this point basically.

Looks like a combination of quicksort and natural mergesort. The answer to your original question: it is as you said: just merge it with the closest newly merged partition.

For STL vectors you could "splice" followed by "sort".