How to Merge Two Sorted Arrays into a Sorted Array

How to merge two sorted arrays into a sorted array?

A minor improvement, but after the main loop, you could use System.arraycopy to copy the tail of either input array when you get to the end of the other. That won't change the O(n) performance characteristics of your solution, though.

O notation and merging two already sorted arrays

Your task is to implement the merge phase of the mergesort algorithm. mergesort has a complexity of O(N.log(N)) to sort the dataset, but each merge phase takes linear time proportional to the length of the merged set.

Here is pseudo code for this:

merge(array a, array b into array c)
    int i = 0, j = 0, k = 0;
    while (i < len(a) and j < len(b)) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < len(a)) {
        c[k++] = a[i++];
    }
    while (j < len(b)) {
        c[k++] = b[j++];
    }
}

The complexity is linear as each step in each of the loops copies an element into the c array, for a total of len(a) + len(b) steps.

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

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!

Merge two sorted arrays in java

This is well explained in multiple places on the Internet. Take a look at Java program to merge two sorted arrays which showes a graphical explanation of the algorithm. You can change your method to use a single while loop as:

public static int[] merge(int[] arr1, int[] arr2) {
  if (arr1 == null && arr2 == null) return null;
  if (arr1 == null) return arr2.clone();
  if (arr2 == null) return arr1.clone();       

  int[] result = new int[arr1.length + arr2.length];
  int i = 0, j = 0, r = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result[r] = arr1[i];
      i++;
    } else {
      result[r] = arr2[j];
      j++;
    }
    r++;
  }
  // Copy the remaining elements in array 1 to result
  if (i < arr1.length) {
    System.arraycopy(arr1, i, result, r, (arr1.length - i));
  }
  // Copy the remaining elements in array 2 to result
  if (j < arr2.length) {
    System.arraycopy(arr2, j, result, r, (arr2.length - j));
  }
  return result;
}

Merging two sorted arrays with 'for' loop... how to stop 'i' from increasing at end of loop

You could take some while loops, because you can independently check the indices and push the values as desired and increment the index for the pushed value.

The first while loop checks both indices and contains a check for getting a smaller value.

The other both while loops are necessary to add the leftover values to the merged array.

var array1 = [1, 3, 6, 7, 11],

    array2 = [2, 3, 5, 8, 9, 10],

    merged = [],

    i = 0,

    j = 0;

while (i < array1.length && j < array2.length) {

    if (array1[i] < array2[j]) {

        merged = [...merged, array1[i++]];

        continue;

    }

    merged = [...merged, array2[j++]];

}

while (i < array1.length) merged = [...merged, array1[i++]];

while (j < array2.length) merged = [...merged, array2[j++]];

console.log(...merged);

Merging Two Sorted Arrays with O(log(n+m)) Worst Case

I don't think there is an algorithm that would merge two arrays in O(log(n+m)) time.

And it makes sense when you think about it. If you're trying to create a new sorted array of n+m elements you will need to do at least n+m copies. There is no way getting around that.

I think the best way would be to iterate through each array simultaneously and, at each iteration, compare the values of both elements. If one is less than the other (if you want the array sorted in descending order), then copy that element to the array and increment your indexing pointer for that array and vice versa. If the two elements are the same, you can just add them both into the newly sorted array and increment both pointers.

Continue until one of the pointers has reached the end of its respective array and then copy in the rest of the other array once one has.

That should be O(m+n)

Regarding your edit, there is a way to find the median of two separate arrays in log(n + m) time.

You can first find the median of the two sorted arrays (the middle element) and compare them. If they are equal, then that is the median. If the first's median is greater than the second's you know the median has to be in either the first half of the first array or the second half of the second array and vice versa if the first's median is less than the second's.

This method cuts your search space in half each iteration and is thus log(n + m)

numpy: How to merge two sorted arrays into a larger sorted array?

Abusing the sorted nature of the input arrays, we can use np.searchsorted, like so -

def merge_sorted_arrays(a, b):
    m,n = len(a), len(b)
    # Get searchsorted indices
    idx = np.searchsorted(a,b)

    # Offset each searchsorted indices with ranged array to get new positions
    # of b in output array
    b_pos = np.arange(n) + idx

    l = m+n
    mask = np.ones(l,dtype=bool)
    out = np.empty(l,dtype=np.result_type(a,b))
    mask[b_pos] = False
    out[b_pos] = b
    out[mask] = a
    return out

Sample run (using a generic case of duplicates) -

In [52]: a
Out[52]: array([1, 2, 3, 3, 5, 9, 9, 9])

In [53]: b
Out[53]: array([ 2,  4,  6,  6,  6,  7, 10])

In [54]: merge_sorted_arrays(a, b)
Out[54]: array([ 1,  2,  2,  3,  3,  4,  5,  6,  6,  6,  7,  9,  9,  9, 10])

Timimgs on random-sorted 1000000 sized arrays -

Benchmarking against the popular concatenate+sort method.

# Setup
In [141]: np.random.seed(0)
     ...: a = np.sort(np.random.randint(0,1000000,(1000000)))
     ...: b = np.sort(np.random.randint(0,1000000,(1000000)))

# @chmod777's soln
In [142]: %%timeit
     ...: c = np.concatenate((a,b), axis=0)
     ...: c.sort()
141 ms ± 2.13 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [143]: %timeit merge_sorted_arrays(a, b)
55.1 ms ± 5.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

---

Related Topics