Skip to content

Instantly share code, notes, and snippets.

@nashid
Last active November 1, 2016 23:19
Show Gist options
  • Save nashid/b4375cb458f8d8a595d5ba614bfef729 to your computer and use it in GitHub Desktop.
Save nashid/b4375cb458f8d8a595d5ba614bfef729 to your computer and use it in GitHub Desktop.
Given two sorted arrays merge them into a new array and keep the merged array sorted
package kata;
import java.util.Arrays;
/*
* input1 = { 3, 8, 17, 99}
* input2 = { 5, 17, 88}
* output = { 3, 5, 8, 17, 88, 99}
*/
public class MergeSortedArray {
private static void print(int input[]) {
if (null == input || input.length == 0) {
System.out.println("null Or Empry");
return;
}
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
System.out.println();
}
public static int[] mergeArrayWithNewArray(int input1[], int input2[]) {
int output[] = new int[input1.length + input2.length];
int p1 = 0, p2 = 0, out = 0;
while (p1 < input1.length && p2 < input2.length) {
if (input1[p1] < input2[p2]) {
output[out++] = input1[p1++];
}
else if (input1[p1] == input2[p2]) {
output[out++] = input1[p1++];
output[out++] = input2[p2++];
}
else {
// input1[p1] > input2[p2]
output[out++] = input2[p2++];
}
}
// p1 contains greater value
while (p1 < input1.length) {
output[out++] = input1[p1++];
}
// on the other hand p2 contains greater numbers
while (p2 < input2.length) {
output[out++] = input2[p2++];
}
return output;
}
/*
* merge two sorted array array1 and array2 into the array1 (array1 has enough space)
*/
public static int[] mergeArray(int input1[], int input2[], int array1Length) {
int p1 = array1Length-1, p2 = input2.length-1;
int out = array1Length + input2.length -1;
while( index1 > 0 && index2>=0 ) {
if(input1[p1] < input2[p2]) {
input1[out--] = input2[p2--];
}
else {
input1[out--] = input1[p1--];
}
}
while(p2>=0) {
input1[out--] = input2[p2--];
}
return input1;
}
public static void main(String args[]) {
System.out.println(Arrays.toString(mergeArray(new int[]{}, new int[]{})));
System.out.println(Arrays.toString(mergeArray(new int[]{3, 8, 17, 99},
new int[]{5, 17, 88})));
System.out.println(Arrays.toString(mergeArray(new int[]{},
new int[]{5, 17, 88})));
System.out.println(Arrays.toString(mergeArray(new int[]{3, 8, 17},
new int[]{})));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment