0

I have 4 sorted parts in one big array. For example big array has a 100 items and sorted parts are on indexes: 0-24, 25-49, 50-74, 75-99.

What is the best way to sort the whole array? I really prefer a Merge sort algorithm.

Thank you very much for some ideas.

1

3 Answers 3

3

You don't need to do a merge sort. You just need to do the merge operations in-place 3 times (1st part merge 2nd part; 3rd part merge 4th part; then merge those two). Note that merge is an O(n) operation, which is what makes a merge sort work. So this algorithm will be O(n) + O(n) + O(n) = O(n).

O(n) is optimal since you will need to access each element at least once no matter what. (So the problem, and this algorithm, are Omega(n) and Theta(n) as well, for what it's worth.)

6
  • How is a simple merge supposed to be sufficient? The elements are already in one big array with the 4 parts being sorted internally. Merging would essentially create a copy of the big array.
    – Jonas
    Commented Nov 25, 2015 at 17:16
  • Could you explain why a simple merge is sufficient?
    – Jonas
    Commented Nov 25, 2015 at 17:33
  • @Jonas You do a merge operation in-place 3 times - merge 1st part and 2nd part, merge 3rd part and 4th part, then merge the two resulting chunks.
    – djechlin
    Commented Nov 25, 2015 at 17:50
  • How does that ensure that the big array is sorted? A merge is simply the the act of joining two separate parts together. The way the problem is described you are given 4 sorted arrays which has to be turned into 1 big sorted array. You are given no guarantees about the ordering of the 4 parts.
    – Jonas
    Commented Nov 25, 2015 at 18:07
  • @Jonas yes, that's correct. The merge operation in a merge sort requires the input arrays be sorted, not that one is ordered before the other one.
    – djechlin
    Commented Nov 25, 2015 at 18:09
2

You need to use std::inplace_merge

std::vector<int> data(100);
// fill data array
auto it1 = data.begin();
auto it2 = data.begin() + 25;
auto it3 = data.begin() + 50;
auto it4 = data.begin() + 75;
auto it5 = data.begin() + 100;
std::inplace_merge(it1, it2, it3); // merge it1-it2 and it2-it3
std::inplace_merge(it3, it4, it5); // merge it3-it4 and it4-it5
std::inplace_merge(it1, it3, it5); // merge it1-it3 and it3-it5
0

You can use a regular bottom up merge, but since you have 4 sorted groups with 25 elements each, initialize the bottom up merge sort run size (width) to 25. You can follow the code in the wiki example, except use std::swap(A, B) after each pass instead of the copy back loop. Since 100 is a multiple of n, you don't need the min checks.

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

Something like this:

#define n 100
// array A[] has the items to sort; array B[] is a work array
// in this case data ends up back in A[]
void BottomUpMergeSort(int A[], int B[], int n)
{
    for (int width = 25; width < n; width = 2 * width){
        for (int i = 0; i < n; i = i + 2 * width)
            BottomUpMerge(A, i, i+width, i+2*width, B);
        std::swap(A, B);
    }
}

void BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[])
{
    int i0 = iLeft;
    int i1 = iRight;
    int j;
    for (j = iLeft; j < iEnd; j++){
        if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
          B[j] = A[i0++];
        else
          B[j] = A[i1++];
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.