How Can I Efficiently Merge Two Sorted Arrays?

How to Merge Two Sorted Arrays Efficiently

In a recent interview, you were asked to merge two sorted arrays into a single sorted array. You provided a solution that involved comparing elements and appending them to a new array. While this approach is correct, it can be optimized for better performance.

Here is a more efficient solution:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length) {
        answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
    }

    while (i < a.length)
        answer[k++] = a[i++];

    while (j < b.length)
        answer[k++] = b[j++];

    return answer;
}

The optimized solution uses a single loop to iterate over both arrays and merge them into the answer array. By using the ternary operator (? :), we can determine the smaller element and append it to the answer array without requiring an additional conditional statement.

Additionally, we use k to increment the index of the answer array after each element is added, simplifying the code and reducing the number of operations.

Compared to the original solution, this optimized version is more concise and executes with fewer conditional checks, resulting in improved efficiency.

The above is the detailed content of How Can I Efficiently Merge Two Sorted Arrays?. For more information, please follow other related articles on the PHP Chinese website!