using System;
// Given two sorted arrays, merge them into a single sorted array
// Example:
// array1: {0, 3, 4, 31}
// array2: {4, 6, 30}
// merged: {0, 3, 4, 4, 6, 30, 31}
class MainClass {
static void Main() {
int[] array1 = {0, 3, 4, 31};
int[] array2 = {4, 6, 30};
Console.WriteLine("array1 = " + toString(array1));
Console.WriteLine("array2 = " + toString(array2));
Console.WriteLine("merged = " + toString(merge(array2, array1)));
}
static int[] merge(int[] a1, int[] a2) {
int[] m = new int[a1.Length + a2.Length];
int a1CurrentIndex = 0;
int a2CurrentIndex = 0;
for (int i = 0; i < m.Length; i++) {
//Console.WriteLine("a1CurrentIndex = " + a1CurrentIndex + ", a2CurrentIndex = " + a2CurrentIndex);
if (a2CurrentIndex == a2.Length) {
m[i] = a1[a1CurrentIndex];
a1CurrentIndex++;
} else if (a1CurrentIndex == a1.Length) {
m[i] = a2[a2CurrentIndex];
a2CurrentIndex++;
} else if (a1[a1CurrentIndex] < a2[a2CurrentIndex]) {
m[i] = a1[a1CurrentIndex];
a1CurrentIndex++;
} else {
m[i] = a2[a2CurrentIndex];
a2CurrentIndex++;
}
//Console.WriteLine("m = " + toString(m));
}
return m;
}
static string toString(int[] array) {
string s = "{";
for (int i = 0; i < array.Length; i++) {
if (i > 0) {
s += ", ";
}
s += array[i];
}
s += "}";
return s;
}
}