Can any one give me better solution for merging two sorted arrays into another sorted array

Question

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arrA = {2,3,4};
        int[] arrB = {5,6,7,8};
        mergeArray(arrA,arrB);
    }
    static void mergeArray(int[] arrA,int[] arrB){

        int len = arrA.length+arrB.length;
        int lenA = arrA.length;
        int lenB = arrB.length;
        int a=0,b=0,c=0;
        int temp=0;
        int[] arrC = new int[len];
        for(int i=0; i < lenA; i++){
            arrC[i] = arrA[i];
        }
        for(int j=lenA,k=0; (k < lenB) && (j < len) ; j++,k++){
            arrC[j] = arrB[k];
        }
        for(int n=0; n < len ; n++){
            for(int m=0; m < len; m++ ){
                if(arrC[n] < arrC[m]){
                    temp  = arrC[n];
                    arrC[n] = arrC[m];
                    arrC[m] = temp;
                }
            }
        }
        for(int x : arrC){
            System.out.println(x);
        }
    }

Result: {2,3,4,5,6,7,8}

I am trying to put the values into one new array and sorting them again.Can any one give me better solution than this.

Answer 1

Easy. You're concatenating one array after another, then doing a bubble sort. A bubble sort is O(n^2) in the worst case. This means that the time needed to sort may increase with the square of the sum of the lengths of the two input arrays.

But you already know that the two arrays are ordered. When writing to the combined array, all you need to look at are the heads of the two input arrays. The next write will be the minimum value of the two. Your merge will be O(n), where n is the sum of the lengths of the two input arrays.

This is one part of a sorting algorithm called merge sort. Frequently a merge sort is in-place, in a single array. Yours differs slightly, with the two sorted parts in separate arrays, but the idea is the same.

Answer 2

You can use Java8 Streams:

    int[] arrA = {2,3,4};
    int[] arrB = {5,6,7,8};
    int[] mergedArray = IntStream.concat(Arrays.stream(arrA), Arrays.stream(arrB)).toArray();

If the order is important:

IntStream.concat(Arrays.stream(arrA), Arrays.stream(arrB)).sorted().toArray();

In such case you can convert it not only to an array, but to whatever you want.

Answer 3

I recalled old school days! Here is the solution! No libraries, just plain code! Enjoy.

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int [] array1 = {5, 1, 4, 5, 7, 8, 1, 0, 4};
        int [] array2 = {4, 7, 1, 0, 9, 3};

        System.out.println("Array 1");
        print(array1);

        System.out.println("Array 2");
        print(array2);

        Arrays.sort(array1);
        Arrays.sort(array2);

        System.out.println("Sorted array 1");
        print(array1);

        System.out.println("Sorted array 2");
        print(array2);

        int [] mergedAndSortedArray = mergeSorted(array1, array2);

        System.out.println("Sorted merged array");
        print(mergedAndSortedArray);
    }

    private static void print(int [] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }

        System.out.println("\n");
    }

    private static int [] mergeSorted(int [] array1, int [] array2) {
        int [] res = new int [array1.length + array2.length];

        int i = 0;
        int j = 0;
        int k = 0;

        //Do your homework. First loop until you reach end of either array, and then add the rest elements.

        return res;
    }
}

This is result

Array 1
5 1 4 5 7 8 1 0 4 

Array 2
4 7 1 0 9 3 

Sorted array 1
0 1 1 4 4 5 5 7 8 

Sorted array 2
0 1 3 4 7 9 

Sorted merged array
0 0 1 1 1 3 4 4 4 5 5 7 7 8 9 

Update

If you need to merge N sorted arrays into a sorted one, you can merge them by pairs recursively (merge first and second arrays, third and fourth, and so on), then again, until you have two arrays, and finally merge them too!

Answer 4

Try this:

Integer[] mergeArray = (Integer[])ArrayUtils.addAll(arrA, arrB);

Checkout this:

public static T[] addAll(T[] array1, T... array2)

And then:

Arrays.sort(mergeArray, Collections.reverseOrder());

Answer 5

I think you're asking for a way to "zip together" two arrays that are already sorted, so that you end up with a sorted array. I think you've realised that concatenating then sorting is inefficient, because it doesn't take advantage of the input arrays being sorted already.

I also assume that this is a homework or study question, so I'm going to describe the solution at a high level.

You need a few variables to track where you are:

• leftIndex (where you are on the left input)
• rightIndex (where you are on the right input)
• destinationIndex (where you are in the destination)

Start with all the indexes at zero. Now we're going to pick an array to work from, and take values from it one by one.

As long as those values are less than the next value from the other input array, we add it to the output. Then we switch over to the other array. We keep switching back and forth until we've reached the end of both inputs.

Pseudocode:

while (leftIndex and rightIndex are both within the length of their arrays) {
    while(leftInput[leftIndex] is less than rightInput[rightIndex]) {
         copy leftInput[leftIndex] into destination[destinationIndex]
         increment leftIndex
         increment destinationIndex
    }
    while(rightInput[rightIndex] is less than leftInput[leftIndex]) {
         copy rightInput[leftIndex] into destination[destinationIndex]
         increment rightIndex
         increment destinationIndex
    }
}

If you translate what I've written directly into Java, you'll probably get ArrayIndexOutOfBounds exceptions. You need to add extra code in the while statement to make it do the right thing when one of the indexes is past the end of its array.