Merge Two Sorted Arrays

Problem Statement

Write a method named merge that takes two sorted integer arrays as input and returns a new sorted array containing all elements from both input arrays in ascending order.

Function Signature

public static int[] merge(int[] array1, int[] array2)

• Input:
  • array1: A sorted integer array
  • array2: A sorted integer array
• Output:
  • A new sorted integer array containing all elements from array1 and array2

Example

Example 1

int[] array1 = {1, 3, 5, 7};
int[] array2 = {2, 4, 6, 8};
int[] result = merge(array1, array2);
System.out.println(Arrays.toString(result));

Output:

[1, 2, 3, 4, 5, 6, 7, 8]

Example 2

int[] array1 = {10, 20, 30};
int[] array2 = {5, 15, 25, 35};
int[] result = merge(array1, array2);
System.out.println(Arrays.toString(result));

Output:

[5, 10, 15, 20, 25, 30, 35]

Example 3

int[] array1 = {};
int[] array2 = {1, 2, 3};
int[] result = merge(array1, array2);
System.out.println(Arrays.toString(result));

Output:

[1, 2, 3]

---

Constraints

1. array1 and array2 are both sorted in ascending order.
2. array1.length + array2.length ≥ 1 (At least one element is present).
3. The method must use a linear time complexity O(N), where N = array1.length + array2.length.
4. The function must not modify the input arrays and should return a new array.

---

1. first approach

 

1.

public static int[] merge(int [] arr1, int[] arr2){
    int i = 0;
    int j = 0;
    int[] result = new int[arr1.length + arr2.length];

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result[i + j] = arr1[i]; 
            i++;
        } else if (arr1[i] > arr2[j]) {
            result[i + j] = arr2[j];  
            j++;
        }
    }

    if (i == arr1.length) {  
        while (j < arr2.length) {
            result[i + j] = arr2[j];  
            j++;
        }
    } else {
        while (i < arr1.length) {   
            result[i + j] = arr1[i];  
            i++;
        }
    }

    return result;
}

 

2. better

public static int[] merge(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, index = 0;

    while (i < arr1.length && j < arr2.length) {
        result[index++] = (arr1[i] < arr2[j]) ? arr1[i++] : arr2[j++];
    }

    while (i < arr1.length) {
        result[index++] = arr1[i++];
    }

    while (j < arr2.length) {
        result[index++] = arr2[j++];
    }

    return result;
}