minimalist bottom up merge sort

Code:

---

typedef vector<int> LIST; // LIST can be a vector of any comparable type

static LIST merge_sort(LIST &linp)
{
size_t i, width;

    LIST lout(linp.size()); // second list for output

    for(width = 1; width < linp.size(); width *= 2){ /* merge pass */
        for(i = 0; i < linp.size(); i += 2 * width){ /* merge sublists */
            merge_pair(lout, linp, i, min(i+width, linp.size()), min(i+2*width, linp.size()));
        }
        linp.swap(lout);    // swap lists (if optimized would swap ptrs)
    }
    return(linp);          // return sorted list
} 

static void merge_pair(LIST &lout, LIST &linp, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;

/*  merge a pair of sublists */
 
    for (size_t iout = ileft; iout < iend; iout++){
        if (il < iright && (ir >= iend || linp[il] <= linp[ir]))
            lout[iout] = linp[il++];
        else
            lout[iout] = linp[ir++];
    }
}

---

Do you have a question or problem with this code?

Jim

Quote:

---

Originally Posted by jimblumberg

Do you have a question or problem with this code?

---

No, but I noticed that there is an article for top down merge sort here:

Merge Sort - Cprogramming.com

but no article for bottom up merge sort, so I thought I'd post this minimal code version as an example. It would be nice to have an article for bottom up merge, since this is the more common implementation in the case of program libraries, standard template libraries, and commercial products.

All that is accomplished during the recursion phase of a "classic" top down sort is repeated splitting of a list or creation of a binary tree of indexes until list or pair of indices represent a list size of 1, which takes n-1 split operations. It's needless overhead since a list of n elements could be considered as n sub-lists of size 1 without performing any code, which is what bottom up merge sort does.

A partial top down merge sort could be used to reduce memory overhead, such as allocating a second buffer 1/2 the size of a list, then sorting each half of the list, ending up with the sorted first half of the list in the second buffer, and the sorted second half of the list in the second half of the original list, then doing a final merge back into the original list.

Quote:

---

Originally Posted by rcgldr

Code:

---

typedef vector<int> LIST; // LIST can be a vector of any comparable type

static LIST merge_sort(LIST &linp)
{
size_t i, width;

    LIST lout(linp.size()); // second list for output

    for(width = 1; width < linp.size(); width *= 2){ /* merge pass */
        for(i = 0; i < linp.size(); i += 2 * width){ /* merge sublists */
            merge_pair(lout, linp, i, min(i+width, linp.size()), min(i+2*width, linp.size()));
        }
        linp.swap(lout);    // swap lists (if optimized would swap ptrs)
    }
    return(linp);          // return sorted list
} 

static void merge_pair(LIST &lout, LIST &linp, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;

/*  merge a pair of sublists */
 
    for (size_t iout = ileft; iout < iend; iout++){
        if (il < iright && (ir >= iend || linp[il] <= linp[ir]))
            lout[iout] = linp[il++];
        else
            lout[iout] = linp[ir++];
    }
}

---

---

Okay so it's just a code review then... :)

Lose the typedef, or at the very least do not call a vector a list. Whenever someone calls something that uses a contiguous block of memory a "list", simply causes confusion. It meets the mathematical definition of a list, but that is where it ends. In C++ a vector is best described using the word "array".

Lose the static keyword. That either means it can't be used outside of this source file, or it means that you've needlessly thrown this into a class even though it touches no member variables at all.

Lose the return value. You're passing in a vector by reference and modifying it into sorted order. There is probably no need to also return the vector, and risk having the compiler copy the entire container, at least in debug builds, which has thus far nicely been avoided.

This comment shows a misunderstanding:

Quote:

---

// swap lists (if optimized would swap ptrs)

---

vector::swap is specified as a constant-time, non-throwing, operation. Thus it can only ever be performed by a pointer swap internally. There are no if's about it.

I do not like some of your variable names e.g. "linp" & "lout".

Rather than calling this "bottom-up" merge sort, the term usually used is "breadth-first", as opposed to the common "depth-first".

Psst, check out the relevant link in my signature...

Well I had a long reply in the works only to have this forum lock up with a database error, and losing my reply. Where does the "autosave" data go? It locked up my browser (google chrome), which prevented me from doing a copy of the text I was working on. I'll do a full reply later.

Quote:

---

Originally Posted by iMalc

Rather than calling this "bottom-up" merge sort, the term usually used is "breadth-first", as opposed to the common "depth-first".

---

Do a web search for "bottom up merge sort" versus "breadth first merge sort", you find quite a few hits for both. Wiki calls it "bottom up", and so do most older text books (note, old guy here, I'm 61 years old). "Breadth first" is more commonly used in reference to tree traversal, do a web search for "breadth first", and you'll see evidence of this. Then again, "bottom up" is an even more generic term.

I plan to clean up my example code and repost to this thread later. Any other suggestions?

continuing ...

Quote:

---

Originally Posted by iMalc

do not call a vector a list.

---

This example was posted at the wiki talk page for merge sort, where the term list was used throughout the article, so the example was just following the terminology used there. There's no need to use that here so I'll change it. Normally I would call it vdata (vector of data) or vsrc (source).

Quote:

---

Originally Posted by iMalc

Lose the static keyword.

---

Old habit from some corporate standards, I'll remove it.

Quote:

---

Originally Posted by iMalc

Lose the return value.

---

edit - your correct, swap() will put the data into the original list.

Quote:

---

Originally Posted by iMalc

vector::swap is only ever be performed by a pointer swap internally.

---

Again a holdover from the fact that it was a proposed wiki section, where language specific actions needed to be explained to potential readers not aware of this. I'll update the comment.

Quote:

---

Originally Posted by iMalc

I do not like some of your variable names e.g. "linp" & "lout".

---

I'm thinking vsrc (source) and vdst (destination) would be better.

Quote:

---

Originally Posted by iMalc

Rather than calling this "bottom-up" merge sort, the term usually used is "breadth-first", as opposed to the common "depth-first".

---

As mentioned above, "breadth first' and "depth first" are terms more commonly used in reference to tree structures. Using bing, or google, I'm find more hits for "bottom up merge sort" than I do "breadth first merge sort" (144 versus 9 in case of bing). In my opinion, "bottom up" makes more sense because it's an iteration of indices or pointers instead of dealing with any type of tree structure.

I plan to clean up my example code and repost to this thread later. Any other suggestions?

Quote:

---

Originally Posted by rcgldr

Then again, "bottom up" is an even more generic term.

---

Bottoms up! :)

Quote:

---

Originally Posted by rcgldr

Old habit from some corporate standards, I'll remove it.

---

In the event that you do want to use it to specify internal linkage, the conventional approach in C++ is to use an unnamed namespace instead.

Quote:

---

Originally Posted by rcgldr

I'm thinking vsrc (source) and vdst (destination) would be better.

---

Why not just source and destination?

Quote:

---

Originally Posted by rcgldr

As mentioned above, "breadth first' and "depth first" are terms more commonly used in reference to tree structures. As mentioned in my partial reply, web searches using these terms will show this. In my opinion, "Bottom up" makes more sense because it's an iteration of indices or pointers instead of dealing with any type of tree structure.

---

The way I see it, there is an implicit tree involved. However, normal breadth first traversal starts from the immediate children of the root, whereas this starts from the leaves of a complete tree, so in that sense "breadth first" is not an apt description.

Okay, I've been convinced that bottom-up might technically be the better term for the way it is being done here. I'll take that back.

Here's the updated code:

Code:

---

typedef vector< ... > VECTOR;

void merge_sort(VECTOR &vsrc)
{
size_t i, width;

    VECTOR vdst(vsrc.size()); // second vector used for merge algorithm

    for(width = 1; width < vsrc.size(); width *= 2){ // merge pass
        for(i = 0; i < vsrc.size(); i += 2 * width){ // merge sublists
            merge_pair(vdst, vsrc, i, min(i+width, vsrc.size()), min(i+2*width, vsrc.size()));
        }
        vsrc.swap(vdst);    // swap ptrs for merged data back to vsrc
    }
} 

void merge_pair(VECTOR &vdst, VECTOR &vsrc, size_t ileft, size_t iright, size_t iend)
{
size_t il = ileft;
size_t ir = iright;

//  merge a pair of sublists
 
    for (size_t idst = ileft; idst < iend; idst++){
        if (il < iright && (ir >= iend || vsrc[il] <= vsrc[ir]))
            vdst[idst] = vsrc[il++];
        else
            vdst[idst] = vsrc[ir++];
    }
}

---

Note that sort() and stable_sort() in the Standard Template Library reverse the compare parameters so that the compare operator is less than and true means the elements are out of order. This would look like:

Code:

---

        if (ir < iend && (il >= iright || vsrc[ir] < vsrc[il]))
            vdst[idst] = vsrc[ir++];
        else
            vdst[idst] = vsrc[il++];

---

I didn't do it this way because it seems more logical to not reverse the order of the parameters. I'm not sure why the STL sort compares were implemented that way.

Code:

---

size_t i, width;
for(width = 1; width < linp.size(); width *= 2){
    for(i = 0; i < linp.size(); i += 2 * width){

for (size_t iout = ileft; iout < iend; iout++){

---

O_o

Marked for inconsistent style and naming. Move the controllers, loop variables, to the smallest scope in the first block as in the second. Adjust the style for consistent spacing.

Also, the `merge_pair' function is logically a part of `merge_sort'; you should consider putting at least `merge_pair' in a namespace to reduce the burden on global scope.

Finally, it is trivial to generalize this over the element type.

Code:

---

void merge_sort(std::vector<int> & vsrc)

---

Code:

---

template
<
    typename FElement
  , typename FAllocator
>
void merge_sort(std::vector<FElement, FAllocator> & vsrc)

---

The `FAllocator' is part of the expansion for standard template containers; you don't need to know what it does to generalize the expansion of a specific container.

[Edit]
Yes, for those of you in the know, I am ignoring parts of the standard.

I've done it with purpose; the lacking standard over possible extra template parameters of the standard containers is silly.

It can be solved, but then it is no longer trivial to generalize over the element type, and is only useful if the client code specifically uses the non-standard parameters.
[/Edit]

Soma

Note I posted another example a few minutes before your reply, so we cross posted.

Quote:

---

Originally Posted by phantomotap

Also, the `merge_pair' function is logically a part of `merge_sort'; you should consider putting at least `merge_pair' in a namespace to reduce the burden on global scope.

---

and I got complaints for using statics to reduce global scope. I could use static on just merge_pair.

Also the point of this is minimalist code, enough to understand how bottom up merge sort works, not to be a practical implementation. There are plenty of examples of practical bottom up merge sort on the web already. It would be nice to have an example of bottom up merge sort here at cprogramming.com (there is a top down merge sort algorithm shown at cprogramming.com, but not a bottom up merge sort).

Quote:

---

Note I posted another example a few minutes before your reply, so we cross posted.

---

Well, I read your latest post, but I didn't read the edit until now, but then, the edit came after my post which leaves me wondering if and why you edited the latest post without fixing the other problems.

*shrug*

Quote:

---

Note that sort() and stable_sort() in the Standard Template Library reverse the compare parameters so that the compare operator is less than and true means the elements are out of order.

---

This is wrong. You need to understand the functions.

It could be that you have a different definition for "order" in which case you need to read the documentation so that you can understand the ordering the functions give you.

It could be that you have a different expectation for `operator <' in which case read any good tutorial on the expectations of how the operator is used.

I don't know what is wrong, but you need to stop, think, and study before guessing about the functionality of an API.

Quote:

---

I got complaints for using statics to reduce global scope.

---

O_o

Nope.

You got complaints for using `static' because it either implies an inappropriate class method, incorrectly changes visibility and/or linkage, or uses a form of specifying internal linkage that isn't canonical in C++.

I'm not telling you to use `static' on `merge_pair'. The suggestions by others was correct; you don't want `static'.

I'm telling you to pollute the global namespace as little as possible.

These are very different things.

Quote:

---

Also the point of this is minimalist code, enough to understand how bottom up merge sort works, not to be a practical implementation.

---

Hiding behind "This is minimalist code." is pointless.

I appreciate that you've started this thread for the sake of getting constructive criticism.

That's exactly what I've offered.

Consistency in style and naming makes the code easier to consume. It isn't just this code. I've seen the problems in a lot of your code.

Reducing the scope of variables is expected in C++, and though the idea can be overused, reducing the scope of variables to nearest intent often improves the reasoning of code.

Finally, although it clearly inappropriate to throw full generalization at you, you've already, foolishly in my opinion, started pursuing the implementation of template facilities so not learning basic generalization as applied to simple examples is a mistake.

These are things on which you need to improve.

You have, in the past, posted answers for newbies without noting that you are also a newbie. I asked you to stop for the sake of the path others may be venturing, and as far as I know, you have stopped. There is another side to that, you aren't yet ready to write good C++ examples intended for consumption by newbies. Believe me, I applaud you wanting to help the site, but you need to improve your own understanding of C++ before you start writing such tutorials. For example, consider the naming suggestions by laserlight; you are using some "shortening" that hurts the quality of the code because it increases the level of effort required to reason about the code. None of these problems are all that significant, but they are all things you need to improve in yourself first so that you may also impart such wonderful approach to others you may wish to help.

[Edit]
To be clear, it is foolish to try and consume too much at once. It has nothing to do with you or templates in particular. It is always a mistake to rush beyond an appropriate pace. That notion is especially true for C++ simply because it has so many different facilities to offer. It is easy to be overwhelmed by C++. Feel free to look at posts by some regulars here who found C++ impossible to learn. They are intelligent people, and they could learn C++ with ease, but they rushed in and found "too much" C++ "too fast".
[/Edit]

Soma

Quote:

---

Originally Posted by rcgldr

Note that sort() and stable_sort() in the Standard Template Library reverse the compare parameters so that the compare operator is less than and true means the elements are out of order.

---

update - this only applies to stable_sort(). sort() doesn't require stability so there no requirement on the ordering of "equal" elements by sort(). stable_sort() guarantees the original order on "equal" elements.

Quote:

---

Originally Posted by phantomotap

This is wrong. You need to understand the functions.

---

This is the actual source code from <algorithm>. _First2 occurs later in the vector than _First1:

Code:

---

        if (_DEBUG_LT(*_First2, *_First1))
            *_Dest = *_First2, ++_First2;
        else
            *_Dest = *_First1, ++_First1;

---

Quote:

---

Originally Posted by phantomotap

It could be that you have a different definition for "order".

---

I'm using the conventional meaning of "order", the order of elements in the vector in this case. _First1 occurs before _First2, but the comparison used by stable_sort() is (*_First2 < *_First1), where true means out of order (the later element is less than the earlier element).

I've also confirmed this stepping through the source code with known data.

Quote:

---

This is the actual source code from <algorithm>.

---

Before I begin, I never care about a particular implementation, and neither should you. (Well, feel free to care when you get incorrect results, but you should not otherwise.) You should code to an interface not an implementation. You have again done yourself a disservice in looking at the source without understanding the design decisions.

Now then, I understood you saying "reverse the order of the parameters" as literally reversing the order of comparison. They are using the interface very normally. I do however apologize for the confusion on my part.

You also said "I'm not sure why the STL sort compares were implemented that way." which also seems to suggest that you thought of reversing the order of comparison, but tells me that you are having problems understanding and appreciating the approach regardless of my confusion so let me explain what you've seen and why they do it that way.

(By the way, this would also be in good documentation for the C++ standard library; so again, stop reading the source as it isn't telling you what you need to know. You need to read some good documentation of the current common standard, and preferably also prepare for the C++11 standard.)

So, anyway, the C++ standard library is implemented against very high level concepts borrowed from mathematics. One of the foundations of such concepts is the notion of partitioning and relation through a single interface. One of these concepts is "strict weak ordering". (I'm almost certain laserlight has told you this much, and he has also told you to read the documentation relevant to the concept.)

The importance of the "strict weak ordering" concept is revealed best through generalization. By relying on such semantics we get to assume other partitioning and relationships through the implication. (We assume the `>=' operator, for example, as it relates to the `<' operator.) We get to list a "strict weak ordering" from a single interface and so build many complex partitioning and ordering schemes using only that single interface. We only need a single binary comparator to do vastly different forms of partitioning and sorting. Consider the case of `stable_sort': as you know, it has a couple of overloads, but without the formality of "strict weak ordering" this could not be the case. The `stable_sort' function offers a version depending on an appropriate `operator <' and one with an explicit function. To implement the relevant part of the function as you have implemented in your "Merge Sort", you would require an extra interface. The version built on having the operators available would also require `>=' while the explicit version would require a second comparator as a fourth parameter.

The upshot is extremely appealing: client code need only provide a single interface as a means of implementing partition and relation for many dozens of generalized algorithms. This approach requires less code. It is easier to fulfill the requirements. It is easier to reason about the algorithms.

In short, generalizing the algorithms around such concepts simplifies a lot of the development process; what you are seeing is just a result of those concepts in implementation.

Know look again at the code in post nine that you reason would be how the "STL" would approach the implementation; it does no match the requirements.

I could have explained why the "STL" is generalized in this fashion earlier, but the source itself doesn't fit so I figured you just didn't understand the implementation. I did not appreciate that you didn't understand the underlying reason.

I apologize for the confusion, but though I've said it before, I have to say it again: you are doing yourself a disservice in looking at a particular implementation before you understand the concepts on which the implementation is built.

Soma

Quote:

---

Originally Posted by phantomotap

I did not appreciate that you didn't understand the underlying reason.

---

That was the main issue for me. I've used other sort libraries, which use <= for compare, but these are sort specific, and not part of a generic library where compare is used for multiple algorithms. So I now understand the reason for using < and not <=.

Quote:

---

Originally Posted by phantomotap

You are doing yourself a disservice in looking at a particular implementation before you understand the concepts on which the implementation is built.

---

The reason for looking at the code was to confirm the implementation concept, to make sure I wasn't missing something, plus I can look to see if there's anything "clever" in a particular implementation that could be used for other purposes.

Quote:

---

Originally Posted by phantomotap

Look again at the code in post nine that you reason would be how the "STL" would approach the implementation; it does no match the requirements.

---

I show this in the second code snippet in post #9. It's using < not <=, how is this not meeting the requirements? I also confirmed that the code is working by testing 32MB of psuedo random data and comparing the output versus known working sort programs.