Thread: merge sort - top down versus bottom up

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658

    merge sort - top down versus bottom up

    This is a continuation from this thread about a program that used an insertion sort to sort a list:

    how-to-sort-datas-linked-list-...htm

    The original poster asked for ways to improve this and I mentioned merge sort, and then a discussion evolved about merge sorts. The original poster wasn't responding, so I created this thread with a more descriptive title to continue the discussion.

    Quote Originally Posted by rcgldr View Post
    Top down merge sort requires more memory, since it creates a dynamic tree structure (indexes or pointers or ...) for all the split up lists on the stack, while a bottom up merge takes about 10 variables.uld go into a separate thread about top down versus bottom up merge sort.
    Quote Originally Posted by iMalc View Post
    Completely false.There is no dynamic tree structure to create, I don't know where you got that from. The only memory it takes up is stack space, just a small constant amount per stack frame, with the maximum depth of stack frames being relative to the log of the total number of items in the list.
    The stack contains the tree. For a typical top down merge sort, a depth first (left first) tree is dynamically created and followed during recursions and returns from the main sort function. The initial recursion follows the left fork of the tree to split lists until list size is reduced to 1, at which point the first merge operation takes place. Then the tree is traversed up (merge operations) and down (split operations) until the entire tree is traversed.

    For a list sort, the tree contains head pointers to list. For arrays, the tree contains indexes or pointers into an array.

    Quote Originally Posted by iMalc View Post
    O(log n) memory usage beats O(n) memory usage.
    Bottom up merge does not use O(n) memory space. For a bottom up merge sort on lists, a fixed size array of head pointers to lists can be used, regardless of n. The microsoft STL bottom up list merge sort implementation uses an fixed size array of 23 pointers, plus 2 temp pointers for merge operations. In my example program (link below) I use an array of 32 pointers.

    A basic bottom up merge sort for a list just needs 4 pointers and a few counters to implement a merge sort similar to a tape based merge sort.

    Quote Originally Posted by iMalc View Post
    Check out my implementation here: List Sorting
    On a side note, a natural merge sort is stable if run counts are used instead of relying on compare to determine the boundaries between runs.

    Link to an example program of a bottom up merge sort for a list using an array of 32 list pointers.

    http://rcgldr.net/misc/sortl.zip

    The program currently uses a static array, but this could be changed to a local array and the array reference passed between the two functions that use the array. The program sorts 4,194,304 nodes with psuedo random 64 bit unsigned integers for data. The data is written to a file in order to verify the sorted result (by comparing with known good output).

    The program merges nodes one at a time into the lists pointed to by the array. For i = 0 to 30, array[i] points to a list of size 2^i (or else it's NULL). array[31] list size is not limited. After the initial list is merged into the array, the array lists are merged to create a single sorted list. The microsoft STL implemenation for list sort uses the same method (but I got the idea for this from a summation class function I wrote).

    - - -

    As I posted in that other thread, all that is accomplished during the recursive phase of a top down merge sort is recursively splitting of lists until lists of size 1 are produced, and only then does any actual merging take place.

    The key concept of a merge sort is to repeatedly combine sorted lists by merging them together until a single list is produced, and this is the same for both top down or bottom up.

    If I'm trying to explain bottom up merge sort using 8 numbered cards, the initial state is 8 groups of 1 card each, and the 8 groups of size 1 are merged in pairs to create 4 groups of size 2, which are then merged to form 2 groups of size 4, which are then merged to create 1 group of size 8.

    If I explain the top down approach, I have to start with 1 group of 8 cards, split it to create 2 groups of 4 cards, split those to create 4 groups of 2 cards, and split those to create 8 groups of 1 card, just to get to the bottom up method's initial state.

    In my opinion, the main purpose of top down merge sort is as a learning tool used to teach recursion, similar to implementing factorial or fibonacci via recursion. It's not efficient, but it's useful for teaching recursion.
    Last edited by rcgldr; 08-15-2013 at 05:18 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Maybe it's a matter of semantics, but I've never seen or used, or heard of a top down merge sort, that created a dynamic tree structure. Like Quicksort, it keeps left and right side indices or pointers, to give us the proper range for the current loop.

    Working with a single array, with say a million integers, do you see a faster run-time using bottom-up merge sort, compared to a top down merge sort?

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Adak View Post
    Maybe it's a matter of semantics, but I've never seen or used, or heard of a top down merge sort, that created a dynamic tree structure. Like Quicksort, it keeps left and right side indices or pointers, to give us the proper range for the current loop.
    Those left and right side indices or pointers are part of a logical tree structure used to identify "runs" or "sub-lists". Top down merge sort is a depth first traversal, while bottom up merge sort can be considered breadth first traversal.

    Quote Originally Posted by Adak View Post
    Working with a single array, with say a million integers, do you see a faster run-time using bottom-up merge sort, compared to a top down merge sort?
    Bottom up is faster. I'm not aware of any libraries (the ones that come with compilers) that implement a top down merge sort. The main algorithms I've seen are quick sort or bottom up merge sort.

    Link to zips of example sort programs and a text file showing the time it took the sorts to run on my system.

    http://rcgldr.net/misc/sortv.zip

    http://rcgldr.net/misc/sortp.zip

    sortv.zip contains a collection of programs that sort 4 million pseudo random 64 bit unsigned integers. sortv.cpp uses microsoft sort() (quick sort) or stable_sort (hybrid insertion / bottom up merge sort). msortv.cpp is setup for natural merge sort (which is why it has the run counts) but it's not enabled unless you change a define. hsortv.cpp is hybrid radix (32 bins) / merge sort, using 1GB+ of ram to sort 32mb of data, so it's the fastest. msortv.cpp "cheats" by using conventional pointers instead of vector iterators, since it was based on a C program. Note - all these sorts took less than 1/2 second to sort the data on my system, so there isn't a practical difference in speed between them for this amount of data.

    sortp.zip contains a test file (1 million 10 byte records) and a collection of programs that sort a text file by sorting an array of pointers to the records.
    Last edited by rcgldr; 08-15-2013 at 06:16 AM.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I'll agree with you on the depth first and breadth first traversal comparison. I can't quite accept two pointers on the stack, as a logical tree structure however. It may be just a "depends what you definition of 'is', is" (Thanks Bill Cliinton for this classical gobblety-gook), issue.

    I'll test this out. I'll be surprised if it keeps up with my optimized Quicksort, however.

    [edit]
    Or not. They're all in C++ code, and I'll give you two guesses who does not have a C++ compiler, or an interest in C++.
    Last edited by Adak; 08-15-2013 at 06:59 AM.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Adak View Post
    I'll agree with you on the depth first and breadth first traversal comparison. I can't quite accept two pointers on the stack, as a logical tree structure however.
    It's not just two pointers, it's two pointers per level of recursion. For each level of recursion, there are two recursive calls made, one with the input pointer used for "left half", one with a created pointer for "right half". The recursion continues until list size is 1. For 1 million records, that's 19 levels of recursion, so 38 pointers end up on the stack each time an end node (a list of size 1) of the "tree" is reached. The nested set of pointers represent the current state of the depth first, left first, "tree" traversal.

    Quote Originally Posted by Adak View Post
    They're all in C++ code, and I'll give you two guesses who does not have a C++ compiler, or an interest in C++.
    msortv.cpp can be easily converted to c, since only main() needs to be changed to use allocated arrays instead of vectors to hold the data. All of the sort functions are already "C" functions. If I get the time, I'll make a "C" version of the code.

    - - -

    On a side note, a "classic" tape style merge sort for lists (one using just 4 pointers) could take advantage of the fact that nodes start on 4 byte boundaries, and use the least significant bit of the "next" pointer as an "end of run" indicator. A next pointer of 0 would indicate the end of a list (or optionally, 1 to indicate end of run and end of list). This eliminates the need to keep track of run sizes with counters. (For real tape drives, a single file mark could indicate "end of run", and a double file mark "end of data").
    Last edited by rcgldr; 08-15-2013 at 12:00 PM.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Yes, two pointers per level. I didn't mean to imply otherwise. If the stack wasn't keeping track of this, then it would be a tree, with other appropriate pointers. Without those other pointers, it doesn't appear to me to be a tree - just a stack, doing it's thing.

    As far as vectors - a magnetic field has a vector, centrifugal force has a vector, intercepting aircraft are given a vector. A C++ vector? I have no clue what that is.

    If the recursion selects the smaller of the two parts when the array splits are made, at every level, I believe you'll find that the depth of the recursion is far less than 38 for a sort of a random million numbers. More like 7-12 levels, iirc.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Adak View Post
    They're all in C++ code
    I converted msortv.cpp to a "C" program, msortv.c. Link to zip file:

    http://rcgldr.net/misc/msortvc.zip

    Quote Originally Posted by Adak View Post
    I'll test this out. I'll be surprised if it keeps up with my optimized Quicksort.
    Quick sort should be a bit faster, since the data is psuedo random array of 64 bit unsigned integers (array size is 4,194,304). Use 2^63 == ((unsigned long long)1 << 63) as the mid point value.

    Quote Originally Posted by Adak View Post
    Yes, two pointers per level. I didn't mean to imply otherwise. If the stack wasn't keeping track of this, then it would be a tree, with other appropriate pointers. Without those other pointers, it doesn't appear to me to be a tree - just a stack, doing it's thing.
    In the case of lists, you don't need other pointers (just NULL terminators to indicate the end of sub-lists). In the case of arrays, then you'll need a pointer and count for each sub-array, or a pair of indices (begin, end). A tree structure normally uses linkages for branch nodes, but there's no reason that a collection of pointers or indices on the stack can't be used for the same purpose. If you don't want to call it a tree, then at least note that top down merge order of operation is similar to that of traversing a tree depth first, left first.

    Quote Originally Posted by Adak View Post
    As far as vectors ...
    In programming, since the 1960's a vector is an array. The naming conventions in APL (first released in the 1960's) in order of number of dimensions: 0 => scalar, 1 => vector, 2 => matrix, 3 or more => tensor (APL specific usage). In math, a vector for "n" dimensions is an array of size n, sometimes called an "n tuple".

    Quote Originally Posted by Adak View Post
    If the recursion selects the smaller of the two parts.
    It doesn't. The recursive part of top down merge sort simply splits a list or array in half and calls itself for each half until list or array size becomes 1. Once the size is 1, it just returns that list or array. Then the two lists or arrays returned from a previous call are merged and returned. As mentioned, the order of splitting and merging follows the same path as traversing a tree depth first, left first.
    Last edited by rcgldr; 08-15-2013 at 04:08 PM.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Yes, I now remember merge sort does simply split the array in half. Shows you how much I have used merge sort.

    Thanks for the explanation on the terms: scalar, vector, etc. I'd heard the terms before, but their definitions were never included.

    I've got the file - thanks for the work to get it into C.

  9. #9
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    555
    Your code is not portable even in the slightest (we don't all use windows):
    Code:
    msortv.c:15:29: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘UI64’
    msortv.c:16:26: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘*’ token
    msortv.c:32:1: warning: parameter names (without types) in function declaration [enabled by default]
    msortv.c:33:1: error: unknown type name ‘PUI64’
    msortv.c:33:1: warning: parameter names (without types) in function declaration [enabled by default]
    msortv.c: In function ‘main’:
    msortv.c:37:1: error: unknown type name ‘PUI64’
    msortv.c:37:15: warning: initialization makes integer from pointer without a cast [enabled by default]
    msortv.c:38:1: error: unknown type name ‘PUI64’
    msortv.c:38:15: warning: initialization makes integer from pointer without a cast [enabled by default]
    msortv.c:39:1: error: unknown type name ‘PUI64’
    msortv.c:39:15: warning: initialization makes integer from pointer without a cast [enabled by default]
    msortv.c:40:1: error: unknown type name ‘UI64’
    msortv.c:44:34: error: ‘UI64’ undeclared (first use in this function)
    msortv.c:44:34: note: each undeclared identifier is reported only once for each function it appears in
    msortv.c:45:14: warning: comparison between pointer and integer [enabled by default]
    msortv.c:48:14: warning: comparison between pointer and integer [enabled by default]
    msortv.c:62:14: error: subscripted value is neither array nor pointer nor vector
    msortv.c:74:5: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘clock_t’ [-Wformat]
    msortv.c:85:5: warning: passing argument 1 of ‘fwrite’ makes pointer from integer without a cast [enabled by default]
    /usr/include/stdio.h:712:15: note: expected ‘const void * __restrict__’ but argument is of type ‘int’
    msortv.c:90:9: warning: passing argument 1 of ‘free’ makes pointer from integer without a cast [enabled by default]
    /usr/include/stdlib.h:488:13: note: expected ‘void *’ but argument is of type ‘int’
    msortv.c:92:9: warning: passing argument 1 of ‘free’ makes pointer from integer without a cast [enabled by default]
    /usr/include/stdlib.h:488:13: note: expected ‘void *’ but argument is of type ‘int’
    msortv.c: At top level:
    msortv.c:111:24: error: unknown type name ‘PUI64’
    msortv.c:134:1: error: unknown type name ‘PUI64’
    msortv.c:134:26: error: unknown type name ‘PUI64’
    msortv.c:134:37: error: unknown type name ‘PUI64’
    msortv.c:32:14: warning: ‘MakeGroups’ used but never defined [enabled by default]
    msortv.c:33:14: warning: ‘MergeGroups’ used but never defined [enabled by default]
    Not to mention the fact that it only works with fixed sized, specially generated data...

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by nonpuz View Post
    Your code is not portable even in the slightest (we don't all use windows):
    Try this version:

    http://rcgldr.net/misc/msortvcll.zip

    I just changed these two lines from:

    Code:
    typedef unsigned __int64   UI64;
    typedef unsigned __int64 * PUI64;
    to

    Code:
    typedef unsigned long long   UI64;
    typedef unsigned long long * PUI64;
    Quote Originally Posted by nonpuz View Post
    Not to mention the fact that it only works with fixed sized, specially generated data...
    It's just an example program used for a benchmark of different algorithms. I have more generic programs, but that one was the easiest to convert back to a C program. The specially generated data isn't required, but it's useful to confirm that the final result matches that of known good output by doing a file compare.
    Last edited by rcgldr; 08-15-2013 at 08:14 PM.

  11. #11
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    555
    You can do the same with #include <stdint.h> and uint64_t and it's 100% portable (C99).

    Anyways, I totally agree though, top-down is definitely just a teaching tool and one way to show clearly that it requires an additional STACK (not really a tree) to operate would be to simply attempt to implement top-down merge sort without the use of recursion. You will see that you can't do it without a stack.

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by nonpuz View Post
    You can do the same with #include <stdint.h> and uint64_t and it's 100% portable (C99).
    Microsoft compilers, even up to Visual Studio 2012, are only C89 compliant. The C++ compiler is more up to date, but the C compiler has been stuck with C89 standard for a long time.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by rcgldr View Post
    The stack contains the tree. For a typical top down merge sort, a depth first (left first) tree is dynamically created and followed during recursions and returns from the main sort function. The initial recursion follows the left fork of the tree to split lists until list size is reduced to 1, at which point the first merge operation takes place. Then the tree is traversed up (merge operations) and down (split operations) until the entire tree is traversed.
    No, the stack does not "contain the tree". Because the tree nodes are visited in a depth-first manner, the stack frames only contain a single path from the root to the current node at any given time. That path corresponds precisely with a stack data structure of log n size, not a tree.

    You've changed your tune, earlier you said "n arrays of size 1 (or n/m arrays of size m)" which implies O(n). I realise it can be done in O(1) memory, but not the way you were describing it, and not any more efficiently than a top-down merge sort.

    On a side note, a natural merge sort is stable if run counts are used instead of relying on compare to determine the boundaries between runs.
    My top-down merge sort is stable as it is. I have taken careful measures to guarantee that as I wrote it, and then confirmed it with unit tests.

    In my opinion, the main purpose of top down merge sort is as a learning tool used to teach recursion, similar to implementing factorial or fibonacci via recursion. It's not efficient, but it's useful for teaching recursion.
    It is not useful to claim it is "not efficient". It is actually pretty good, but it's all relative.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by iMalc View Post
    The stack does not "contain the tree". Because the tree nodes are visited in a depth-first manner, the stack frames only contain a single path from the root to the current node at any given time. That path corresponds precisely with a stack data structure of log n size, not a tree.
    I mentioned dynamic tree. Only a partial instance of the tree exists at any one moment, but over time a top down structure does the equivalent of following an entire tree depth first, left first.

    Quote Originally Posted by iMalc View Post
    You've changed your tune, earlier you said "n arrays of size 1 (or n/m arrays of size m)" which implies O(n).
    I don't think you understood my point. A top down sort uses recursion to eventually split all lists until list size is 1. A bottom up merge sort skips this step and the initial state is n arrays of size 1.

    There aren't actually n arrays of size 1, just indices or pointers that are advanced n/2 times through the original array to access those "n" arrays of size 1 to do the initial merge step for a bottom up merge sort. A top down merge sort eventually does the same thing, when the depth first processing finally reaches the final two pairs of arrays of size 1.

    Quote Originally Posted by rcgldr View Post
    On a side note, a natural merge sort is stable if run counts are used instead of relying on compare to determine the boundaries between runs.
    Quote Originally Posted by iMalc View Post
    My top-down merge sort is stable as it is.
    I was referring to your comment in your list merge sort algorithms web page that a natural merge sort was not stable. The instability only occurs if using compares to determine the end of a run. The instability occurs if the first record of one run is greater than the last record of a previous run, causing the two runs to be treated as one run. Using run counts or some other method to determine the end of runs in a natural merge sort preserves stability.

    Quote Originally Posted by iMalc View Post
    It is not useful to claim it is "not efficient". It is actually pretty good, but it's all relative.
    The process of recursively splitting an array or lists is needless overhead. A merge sort can just consider the array or list as n arrays or lists of size 1 as the initial state (which is what a bottom up merge sort does).

    A top down merge sort ends up with multiple instances of sets of indices or pointers stored on the stack as it follows the call chain down and back up. There's a minimum of two indices or pointers (local to the function) for each level of recursion. For a 1 million (up to 2^20) element sort, that's 19 levels of recursion, so 38 indices or pointers when ever the end of the call chain is reached, plus all the instances of those indices or pointers as the call chain is followed down and back up. There is also overhead like return addresses and any other registers that need to be saved. An classic bottom up merge sort needs about 10 to 12 variables regardless of the number of elements to be sorted and just updates them during iteration.

    In a classic bottom up merge sort for n records, there is a total of n-2 merge operations (n/2 + n/4 + n/8 + ... ). A top down merge sort performs the same n-2 merge operations, but in addition there are a total of n-2 split lists operations, just to get to the initial state of a bottom up merge. I don't see the reason for calculating and storing indices or pointers on a stack when all the required values can be generated by addition or incrementing as part of an iteration.

    It's not as bad as implementing factorial via recursion versus iteration, but it's enough overhead that I'm not aware of any compiler library that implements a top down merge sort. The choices are normally quick sort or bottom up merge sort.
    Last edited by rcgldr; 08-16-2013 at 02:42 AM.

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Here are minimal code examples of merge sort using C++ vectors. The top down example is inefficient since it literally splits and merges lists as opposed to logically doing this using vector iterators, but it makes the example easier to read.

    top down
    Code:
    typedef vector<...> LIST;
    
    LIST merge_sort(LIST &list)
    {
    //  if size == 1, consider list sorted and return it
    
        if(1 >= list.size())
            return(list);
    
    //  else split list into two and recursively call merge_sort()
    //  until list size is 1
    
        LIST::iterator middle = list.begin() + (list.size() / 2);   
        LIST left(list.begin(), middle); // left  = 1st half of list
        LIST right(middle,  list.end()); // right = 2nd half of list
        list.clear(); // optional: clear out the no longer needed list
    
        left  = merge_sort(left);
        right = merge_sort(right);
    
    //  merge the two lists returned from previous iterations of merge_sort()
    
        list = merge_pair(left, right);
        return(list);
    }   
    
    LIST merge_pair(LIST &left, LIST &right)
    {
    size_t il  = 0;
    size_t ir = 0;
    
    //  merge two lists and return a single list
     
        LIST list(left.size() + right.size());
    
        for(size_t iout = 0; iout < list.size(); iout++){
            if (il < left.size() && (ir >= right.size() || left[il] <= right[ir]))
                list[iout] = left[il++];
            else
                list[iout] = right[ir++];
        }
    
        return(list);
    }
    bottom up

    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++];
        }
    }
    Last edited by rcgldr; 08-16-2013 at 03:12 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. minimalist bottom up merge sort
    By rcgldr in forum C++ Programming
    Replies: 14
    Last Post: 05-04-2013, 10:31 AM
  2. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM