CODEWITHSUNDEEP
algorithm
algo-geeks
algo-geeks

Reputation: 5438

In-place merge of two arrays

We have an array of size m+n in which m elements are present, in sorted order, and a second array of size n, again in sorted order. We want both of them to be sorted and present in the first array. No third array is supposed to be given.

Example:

   1, 3, 55, 66, 77, _, _, _ 
   5, 9, 20

The answer would be: 

   1, 3, 5, 9, 20, 55, 66, 77

Upvotes: 19

Views: 11391

Answers (4)

user97370
user97370

Reputation:

Do a regular merge but in reverse comparing the largest numbers first, storing (reversed) into the end of the first array going backwards. This way, the elements you're merging are never overwritten (that this works is easy to see if you think about it for a moment).

Upvotes: 31

Yanling
Yanling

Reputation: 303

    // merge the elements in B[] to A[], starting from the last one
    void merge(int A[], int m, int B[], int n) {
       // m-1 and n-1 represent the current element index in A[] and B[] respectively
      while (n > 0) { // there are still elements in B[] not merged
          if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
            A[m+n-1] = A[m-1]; // move current element of A[] to its right position
            --m; // decrease current element index of A[]
          }
         else { // current element in A[] <= current element in B[]
            A[m+n-1] = B[n-1]; // move current element in B[] to its right position
            --n; // decrease current element index of B[]
         }
      }
   }

Upvotes: 2

Yaxiong Zhao
Yaxiong Zhao

Reputation: 21

In-place basically requires we only use "constant" amount of memory, which does not change with different input array sizes. However, the question itself allocate extra amount of memory that is the same to the size of one of the two input arrays, which is O(n) memory in worst case. This basically makes the idea of "in-place" meaningless...

The question might be better phrased as "merge without extra memory", which is a more precise description of its real intention...

Upvotes: 2

Markus Kull
Markus Kull

Reputation: 1477

Move the contents of the first array to the end of the first array, such that the empty elements are now at the beginning. Then merge the two sequences as usual into the first array.

Upvotes: 1

Related Questions