3-way 병합 정렬

이것도 알고리즘 과목의 과제로 나온 것 중 하나이다. 3-way Merge Sort 알고리즘을 짜는 건데 병합 정렬은 수업 시간에 배웠으니 적당히 응용하면 된다. 근데 3-way는 뭐라 번역해야 하지... 3방향? 3등분?

일반적인 2-way 병합 정렬의 시간복잡도가 O(n log_2 n)인데 3-way 병합 정렬은 O(n log_3 n)이다. 언뜻 보면 3-way가 더 빨라 보이지만 삼진 탐색처럼 if 문이 늘어나서 더 느려진다고 한다. 다만 병렬 처리하는 환경에서는 이게 더 유리할 수도 있다고 함.

보통 알고리즘 코드는 C++로 짜는데 Array.Copy 부분을 구현하기가 귀찮아서 걍 C#을 썼다.

using System;

namespace HW1
{
	delegate bool Compare(int a, int b);

	class Program
	{
		static void MergeSort3way(int[] arr, Compare compare)
		{
			if (arr.Length > 2)
			{
				int mid1 = arr.Length / 3;
				int mid2 = arr.Length - mid1;

				int[] arrU = new int[mid1];
				int[] arrV = new int[mid2 - mid1];
				int[] arrW = new int[arr.Length - mid2];

				Array.Copy(arr, 0, arrU, 0, mid1);
				Array.Copy(arr, mid1, arrV, 0, mid2 - mid1);
				Array.Copy(arr, mid2, arrW, 0, arr.Length - mid2);

				MergeSort3way(arrU, compare);
				MergeSort3way(arrV, compare);
				MergeSort3way(arrW, compare);

				Merge(arr, arrU, arrV, arrW, compare);
			}
			return;
		}

		private static void Merge(int[] arr, int[] arrU, int[] arrV, int[] arrW, Compare compare)
		{
			int i = 0, j = 0, k = 0, l = 0;

			while (i < arrU.Length && j < arrV.Length && k < arrW.Length)
			{
				if (compare(arrU[i], arrV[j]))
				{
					if (compare(arrU[i], arrW[k]))
					{
						arr[l++] = arrU[i++];
					}
					else
					{
						arr[l++] = arrW[k++];
					}
				}
				else
				{
					if (compare(arrV[j], arrW[k]))
					{
						arr[l++] = arrV[j++];
					}
					else
					{
						arr[l++] = arrW[k++];
					}
				}
			}
			if (i < arrU.Length)
			{
				Array.Copy(arrU, i, arr, l, arrU.Length - i);
				l += arrU.Length - i;
			}
			if (j < arrV.Length)
			{
				Array.Copy(arrV, j, arr, l, arrV.Length - j);
				l += arrV.Length - j;
			}
			if (k < arrW.Length)
			{
				Array.Copy(arrW, k, arr, l, arrW.Length - k);
				l += arrW.Length - k;
			}
			return;
		}

		static void Main(string[] args)
		{
			int[] arr = { 24, 6, 97, 86, 45, 77, 11, 10, 4, 15 };

			Console.WriteLine("정렬 전");
			for (int i = 0; i < arr.Length; i++)
			{
				Console.Write("{0} ", arr[i]);
			}
			Console.WriteLine();

			MergeSort3way(arr, (a, b) => a < b);
			Console.WriteLine("정렬 후");
			for (int i = 0; i < arr.Length; i++)
			{
				Console.Write("{0} ", arr[i]);
			}
			Console.WriteLine();
			return;
		}
	}
}