Create a sorted array out of 2 arrays

Question

There are 2 arrays given for ex. A = [20,4,21,6,3] B = [748,32,48,92,23......]

assuming B is very large and can hold all the elements of array A.

Find the way in which array B is in (containing all the elements of array A as well) sorted order.

Design an algorithm in the most efficient way.

Answer 1

Smells like homework. Basically, write into array B starting from the end, keeping track of the place you are reading from in both A and B.

Answer 2

Just try it out :

1. Merge the array A into B .

2. Use quick sort algorithm.

Answer 3

This sounds like merge sort algorithm. You will find tons of examples here. You can then modify to suit.

Answer 4

1. Before adding elements from A to B check if by doing that if you exceed the size of the array, if not Merge A into B

2. Then do a quick sort,

But if you just want to merge both arrays into a new arrays where new array has the combine length of both. Here is a jump start for you, try if you can go forward from here...

public double[] combineArrays(double[] first, double[] second) {

 int totalLenth = first.length + second.length;
 double[] newDoubles = new double[totalLenth];
 for (int i = 0; i < first.length; i++) {
  newDoubles[i] = first[i];
 }

 for (int j = first.length; j < newDoubles.length; j++) {
  newDoubles[j] = second[j - first.length];
 }
 return newDoubles;
}

Hope this helps, Good Luck.

Answer 5

Given that your array is integer array, you can use Radix sort algorithm to sort B in linear time, O(n). Wikipedia has a nice write-up and sample python code.

Radix sort is linear with respect to the number of elements. While it also has a dependence on the size of the array, you take it as a constant; just like you take the comparison operator to be constant as well. When sorting bignum for instance, the comparison operator would also depend on the integer size!

Answer 6

You can also modify an insertion sort idea:

0) do all necessary tests: if arrays are null, if bigger array has enough space

1) add small array at the end of the big array

2) do normal insertion sort, but start it at the beginning of the small array

• here if you do quick_sort or some other "quickiest" O(n*log_n) sort, the problem is that you are not using the fact, that both array are sorted. With the insertion sort you are using the fact, that array B is sorted (but not the fact that A is sorted, so maybe we should develop the idea and modify insertion sort to use that fact as well).