0

I got two sorted arrays e.g. (3,4,5) and (1,3,7,8) and I got the combined sorted array (3,4,5,1,3,7,8).

Now I would like to sort the already combined array, without splitting it, but by overwriting it, by making use of the fact that it consists of 2 arrays which had already been sorted. Is there any way of doing this efficiently? I know there are a lot of threads about how to do this, by iterating through the sorted arrays and then putting the values into the new array accordingly, but I haven't seen this type of question anywhere yet. I would like to do this in c, but any help / pseudocode would be very kindly appreciated. Thanks!

Edit: The function which would do the sorting, would only be given the combined array and (maybe ) the length of the other two arrays if needed.

3
  • Instead of spending a lot of time to sort that already merged array, wouldn't it be sooo much easier to change the code that currently throws your two arrays into the single one? You know, that code could simply do a merge while building up that new array?! Instead of first pulling two arrays into one, to then figure how to efficiently re-sort that.
    – GhostCat
    Commented Nov 16, 2016 at 13:26
  • I am not getting you. What did you mean by overwriting and without spiting? Why standard quick or marge sort won't be applicable in your case?
    – Sigcont
    Commented Nov 16, 2016 at 13:26
  • @Sigstop I think he wants to say: I have an array that consists of two sequences of sorted numbers. Is there a way too sort that array based on this knowledge ... without doing a "real" sort; and without creating another new array.
    – GhostCat
    Commented Nov 16, 2016 at 13:27

1 Answer 1

1

If you already have the original sorted arrays, the combined array (note it is not sorted) doesn't really help, except in that your destination storage is already allocated.

There's a well-known and very simple algorithm for merging two sorted ranges, but you can just use std::merge instead of coding it yourself.

Note that only works for non-overlapping input & output ranges: for your amended question, use std::inplace_merge, with the middle iterator set to the first element from your second sequence:

void sort_combined(int *array, size_t total, size_t first) {
    std::inplace_merge(array, array + first, array + total);
}

// and use it like

int combined[] = {3, 4, 5, 1, 3, 7, 8};
const size_t first = 3;
const size_t second = 4;
const size_t total = 7; // == sizeof(combined)/sizeof(*combined)

sort_combined(combined, total, first);

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.