0

I have two sorted arrays, I have to merge two sorted arrays into one without using extra space? I was checking this solution but I am unable to understand it.

Example

Input: ar1[] = {10};
       ar2[] = {2, 3};
Output: ar1[] = {2}
        ar2[] = {3, 10}  

Input: ar1[] = {1, 5, 9, 10, 15, 20};
       ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
        ar2[] = {10, 13, 15, 20}
Improve this question
9
  • 3
    What specifically do you not understand about the solution? Commented May 25, 2020 at 13:58
  • 1
    Take a look at std::merge Commented May 25, 2020 at 14:02
  • Well, the sample "C++" solution is a C solution. That sort of sucks. Commented May 25, 2020 at 14:06
  • If it is the logic/algorithm you don't understand, c++ tag should be removed. If it is some part of the "C++" solution, show appropriate code. Commented May 25, 2020 at 14:12
  • I honestly don't understand why that algo works. Commented May 25, 2020 at 14:13

3 Answers 3

Reset to default
1

Here is a simple algorithm:

  • while last element of ar1 is larger than ar2[0]:
    • swap them.
    • shift the last element of ar1 to its place in ar1,
    • shift the first element of ar2 to its place in ar2,
    • repeat

The space complexity is O(1), the time complexity is O(n2).

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

O(n2) is a too bad time to this task. This problem can be solved without any shifts. That's a part of merge-sort algo.
This is the right answer, force them to list all the requirements!
@Skident: Of course O(n2) is bad, but the requirement for O(1) space complexity is very strong. With O(n) extra space, the time complexity drops to O(n) too.
There is a faster algorithm with O(1) extra space, but it is very complex. It involves dividing the arrays into sqrt(n) segments, using the first segment as a buffer. See the research paper: "Practical in-place merging" by BC Huang, MA Langston, 1988. doi.org/10.1145/42392.42403
1

I'll solve it for the slightly simpler case of "the two arrays are already in one buffer".

// requires: array is a pointer to a buffer of numbers,
// such that from [array, array+middle) is sorted, and [array+middle, array+length)
// is also sorted.
void merge_inplace( int* array, int length );

// This halves the number "gap", rounding up.  Unless the value was 1, in
// which case it returns 0.
int nextgap( int gap ) {
  if (gap==1) return 0;
  return (gap+1)/2;
}

void merge_inplace( int* array, int length ) {
  int gap = nextgap(length); // about half of length

  while (gap != 0)
  {
    int left = 0;
    int right = left+gap;
    while (right < length) {
      // ensure elements at left and right are in correct relative order:
      if (array[left] > array[right])
        std::swap(array[left], array[right]);
      // advance:
      ++left;
      ++right;
    }
    // repeat on a gap half-ish the size:
    gap = nextgap(gap);
  }
}

now operating on two different arrays requires some extra work/logic, but that is mainly about fiddling with the indexes.

The point is that when you have two arrays that are sorted and next to each other, one pass of this "merge far apart, then closer together" algorithm (which has log-length count of subloops; so O(n lg n) steps) is enough to sort it.

Improve this answer

2 Comments

std::swap is c++, the OP tagged the question as c
@chqr the OP edited the solution to requiest C hours after I answerd it.
0

In your examples the arrays are re-sorted. Is it what you need to do?

For this problem you can use the next algorithm:

  1. Use a for loop from 0 to the length of the array1
  2. Compare elements from the array1 and the array2
  3. If an element of the array2 is less than an element of the array1 then swap them
  4. Iterate over the array2 to find a better place of just swapped element

Algorithm:

void reorder(std::vector<int>& arr1, std::vector<int>& arr2)
{
    for (size_t i = 0, j = 0; i < arr1.size(); )
    {
        if (arr1[i] < arr2[j])
        {
            i++;
            continue;
        }

        std::swap(arr1[i], arr2[j]);

        // find a better place for a swapped element in array 2
        for (size_t k = j, l = k+1; l < arr2.size(); k++, l++)
        {
            if (arr2[k] < arr2[l])
                break;
            std::swap(arr2[k], arr2[l]);
        }
    }
}

This algorithm can be improved...

Improve this answer

3 Comments

I'm afraid this does not work as explained.
well, yes the solution is bit more complicated but as both arrays are sorted we do not need to do O(n2)
the code posted in your answer has O(n2) time complexity, even as both arrays are sorted already.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.