Like Tree4Likes

merge sort - top down versus bottom up

This is a discussion on merge sort - top down versus bottom up within the C Programming forums, part of the General Programming Boards category; Simplified version of bottom up merge sort that takes the temp array pointer (b) as a parameter: Code: // tsortbx.h ...

  1. #76
    Registered User
    Join Date
    Apr 2013
    Posts
    1,262
    Simplified version of bottom up merge sort that takes the temp array pointer (b) as a parameter:

    Code:
    //      tsortbx.h - bottom up merge sort
    
    #ifndef min
    #define min(a,b)  (((a) < (b)) ? (a) : (b))
    #endif
    
    template <class T>
    T * MergeSort(T a[], T b[], const size_t n) {
        for(size_t s = 1; s < n; s <<= 1){  // s = run size
            size_t o = 0;                   // init output index
            while(o < n){                   // merge pairs of runs
                size_t l  = o;              // update run indices
                size_t le = min(l+s, n);
                size_t r  = le;
                size_t re = min(r+s, n);
                while(l < le && r < re)
                    b[o++] = (a[l] < a[r]) ? a[l++] : a[r++];
                // copy remaining values
                while (l < le) b[o++] = a[l++];
                while (r < re) b[o++] = a[r++];
            }
            std::swap(a, b);                // swap array ptrs
        }
        return a;                           // return sorted array
    }
    Last edited by rcgldr; 08-24-2013 at 02:34 PM.

Page 6 of 6 FirstFirst 123456
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, 05: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21