Thread: Merge sort (sorted arrays)

  1. #1
    Registered User
    Join Date
    Apr 2007
    Location
    Greece
    Posts
    52

    Merge sort (sorted arrays)

    I have some already sorted arrays of the same type and I want to sort them efficiently into one array. I guess the best method is the merge sort. Each element of these arrays is an object user-defined and has a size of about 8 integers. My question is if it is worthy to create an array of pointers to the elements of these arrays, which pointers will be ordered according to the value of the objects instead of a new array with a copy of the objects.
    For example, given the arrays Objects a[], b[], c[], d[] I create the array Objects *sorted[].

    sorted[0] = &b[0];
    sorted[1] = &d[0];
    sorted[2] = &a[0];
    sorted[3] = &a[1]'
    sorted[4] = &c[0];
    ...

    Note: I don't want to loose the initial arrays from the memory.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I understand you don't want to modify either of the original arrays? But you do expect them to hang around long enough for you use a sorted array of pointers to their items?

    Just create a large array of pointers. You don't even need merge sort. It is simpler than that; all you need to do is perform one merge phase. That should go really fast!

    Memory usage: Creating an array of pointers and sorting based on that uses less memory.
    Speed: 32 bytes isn't too big for an item, and as long as the copy-constructor is trivial it should copy pretty fast, but not as fast as a just writing a pointer.
    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"

  3. #3
    Registered User
    Join Date
    Apr 2007
    Location
    Greece
    Posts
    52
    Indeed. I don't want to modify the original array because I have use of them as they are.
    The point that I have 5 arrays. If I construct the big sorted array using pointers, I need 4 times to do merge. Is it more efficient to use the implementation of the arrays of pointer 4 times or is it better to copy the values each time into one array with the sum of the sizes of the two initial arrays?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You simply want a k-way merge. Here is some sample code for how to implement that (untested):
    Code:
    //Inputs a .. e
    const object a[42]; // can be any length
    //...
    const object e[1337]; // can be any length
    
    //Output
    object *out[42+...+1337];
    
    struct Inputs {
        object *ptr;
        int count;
        bool operator < (const Inputs & b) { return *ptr < *(b.ptr); }
    };
    
    //Setup
    Inputs in[5];
    int alive = 5, idx = 0;
    in[0].ptr = a; in[0].count = 42;
    //...
    in[4].ptr = e; in[4].count = 1337;
    
    while (alive > 0)
    {
        //TODO: Insert basic algorithm here, to sort 'alive' items in array 'in'
        //by what their 'ptr' points to e.g. std::sort(in[0], in[5]);
    
        out[idx++] = in[0].ptr++;
        if (--in[0].count == 0)
            in[0] = in[--alive];
    }
    //Done: output is in the 'out' array.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort
    By Echooo in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2006, 03:16 PM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  3. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 12:09 PM
  4. Merge Sort using a linked list
    By EvenFlow in forum C Programming
    Replies: 0
    Last Post: 10-04-2001, 11:07 PM
  5. merge sort
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-02-2001, 06:58 PM