using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/// <summary>
/// 병합 알고리즘: MergeAlgorithm: 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
/// 두개의 정수 배열을 합치기
/// 단, 꼭 오름차순으로 정렬되어 있어야 함
/// </summary>
class Program
{
static void Main()
{
//[1] Input
int[] first = { 1, 3, 5 }; //오름차순 정렬됨
int[] second = { 2, 4 }; //오름차순 정렬됨
int M = first.Length; int N = second.Length;
int[] merge = new int[M + N]; //병합된 배열 담을 그릇
int i = 0; int j = 0; int k = 0; //i,j,k 관행
//[2] Process
while(i<M && j < N)//둘 중 하나라도 배열의 끝에 도달할 때까지
{
if(first[i] <= second[j])
{
merge[k++]= first[i++];
}
else
{
merge[k++]= second[i++];
}
}
while (i < M) //첫번째 배열이 끝에 도달할 때까지
{
merge[k++] = first[i++];
}
while(j < N)//두 번째 배열이 끝까지 도달할 때까지
{
merge[k++] = second[i++];
}
//[3] Output
foreach (var m in merge)
{
Console.Write(m+"\\t");
}
Console.WriteLine();
}
}
/*int[] first = { 1, 3, 5 };
int[] second = { 2, 4 };
int[] merge = (from o in first select o).Union(from t in second select t).OrderBy(m => m).ToArray();
merge
int[5]
{ 1, 2, 3, 4, 5 }
int[] merge = first.Union(second).OrderBy(m => m).ToArray();
merge
int[5]
{ 1, 2, 3, 4, 5 }*/