Merge two sorted int arrays into a new sorted array in O(n + m) with three indexes.
Solution
Main.java
import java.util.Arrays;
public class Main {
static int[] merge(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < a.length) out[k++] = a[i++];
while (j < b.length) out[k++] = b[j++];
return out;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(merge(new int[]{1, 4, 7, 10}, new int[]{2, 3, 7, 12, 15})));
System.out.println(Arrays.toString(merge(new int[]{}, new int[]{5, 6})));
}
}
Output Verified by compiling and running
[1, 2, 3, 4, 7, 7, 10, 12, 15]
[5, 6]
At each step the smaller front element is copied; when one array runs out, the rest of the other is copied. This is the merge step of merge sort.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!