CODEWITHSUNDEEP
javaalgorithmsorting
user183037
user183037

Reputation: 2579

Sorting 2 arrays

This is an interview question, so the usual bounds apply.

One array has size n and n elements. Second array has size n+m and m elements. Both the arrays are sorted. The question is to move all n+m elements into the second array in a sorted order. O(N) is desired.

There's no mention of not being able to use extra space, but going by the question, it doesn't seem to allow for additional space.

We can simultaneously walk the two arrays (a la Merge Sort) and combine them, but that would need an extra array or extra complexity of moving existing elements down by 1 (which would mean O(N2)).

Update: Here's an example.

Array1: {2, 4, 6, 10}

Array2: {21, 23, 25, , , , }

Answer: {2, 4, 6, 10, 21, 23, 25}

Upvotes: 1

Views: 774

Answers (3)

no.good.at.coding
no.good.at.coding

Reputation: 20371

There's no mention of not being able to use extra space, but going by the question, it doesn't seem to allow for additional space.

You don't need any - you have n elements in one array and m elements in the other. You also have n+m space in the other. It can clearly accommodate the union of the two arrays.

As mentioned in other answers, all you need to is :

  1. Iterate over the two arrays, beginning from the end of each
  2. Compare the two current elements from the two arrays
  3. Write the larger of the two into the last position in the second array (the one with extra space)
  4. Move on the next element in the array you just wrote from and note that the next larger element will be written to a position one before the position you just wrote to, irrespective of whether it already contains an element or not
  5. If you run out of elements in the first array, you're done since the second array elements are already in their right place
  6. If, instead, you run out of elements in the second array, you simply copy all the elements from the first into the second, moving towards the head of the array.
/**
 * Assumes both array are sorted in ascending order
 * Array a has length n and contains n elements
 * Array b has length m+n and contains m elements
 * The merged, sorted array will be returned in b
 */

public void merge(int [] a, int [] b)
{
    //b is the one with m+n space
    int indexA = a.length - 1; //points to last element in a
    int indexB = b.length - a.length - 1; //points to last element in b
    int writeTo = b.length - 1; //points to last free position

    while(indexA > -1 && indexB > -1)
    {
        if(a[indexA] > b[indexB])
        {
            b[writeTo--] = a[indexA--]
        }
        else
        {
            b[writeTo--] = b[indexB--];
        }
    }

    //are there any elements left-over in a?
    //any elements left-over in b will already be in their right place
    while(indexA > -1)
    {
        b[writeTo--] = a[indexA--];
    }
}

Upvotes: 3

Konstantin Komissarchik
Konstantin Komissarchik

Reputation: 29139

Walk the two arrays simultaneously, but from the back of the data rather than the start. Write the sorted data starting from the end of the larger array. You will never need to displace anything. Any data you overwrite will have already been written at its new location further down in the array... O(m+n)

Upvotes: 3

user684934
user684934

Reputation:

Walk them in descending order. O(2N), not O(N^2).

Upvotes: 4

Related Questions