mergesort

[RicePirate]

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?

[cup]

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.

[RicePirate]

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.

[cup]

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".