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}
Shalini Negi
  • 39
  • 3

3 Answers3

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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
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).

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • 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. – Skident May 26 '20 at 05:05
  • This is the right answer, force them to list all the requirements! – Wolfgang Brehm May 26 '20 at 08:23
  • 1
    @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. – chqrlie May 26 '20 at 14:54
  • 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. https://doi.org/10.1145/42392.42403 – kristianp Feb 17 '21 at 01:18
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...

Skident
  • 326
  • 1
  • 5