병합정렬 (Merge Sort)

병합 정렬 (Merge Sort)

병합, 퀵 정렬은 분할 정복법(Divide And Conquer)이라는 동일한 정렬 알고리즘을 사용함
3단계에 걸쳐 작업 
1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할 
2. 정복 : 각각의 작은 문제를 해결 
3. 병합 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

https://www.youtube.com/watch?v=QAyl79dCO_k

using System;
using System.Text;
 
namespace _05
{
    class Solution1{
        public Solution1(){
            var result = this.Fac(4);
            Console.WriteLine(result);
        }
 
        private int Fac(int n){
            if(n == 1||n == 0) return 1;
            else return n * Fac(n-1);
        }
    }
 
    class Solution2{
        public Solution2(){
            for(int i = 0; i<=10; i++){
                var result = Fibo(i);
                Console.WriteLine(result);
            }
        }
 
        private int Fibo(int n){
            if(n == 0) return 0;
            else if( n == 1) return 1;
            else return Fibo(n -1) + Fibo(n-2);
        }
    }
 
    class Solution3{
        public Solution3(){
            this.Print(10);
        }
 
        int Print(int n){
            Console.WriteLine(n);
            //base case
            if(n == 1){
                return 1;
            }else{
                //recursive case 
                return Print(n-1);
            }
        }
    }
 
    class Solution4{
        public Solution4(){
            int[] arr = { 27, 10, 12, 20, 25, 13, 15, 22 };
            //this.Print(arr);
            this.MergeSort(arr);
            this.Print(arr);
        }
 
        private void MergeSort(int[] arr){
            int[] temp = new int[arr.Length];
            this.MergeSort(arr, temp, 0, arr.Length-1);
        }
        public void MergeSort(int[] arr, int[] temp, int start, int end){
            
            if(start < end){
                int mid = (start+end)/2;
                this.MergeSort(arr, temp, start, mid);
                this.MergeSort(arr, temp, mid + 1, end);
                this.Merge(arr, temp, start, mid, end);
            }
        }
        private void Merge(int[] arr, int[] temp, int start, int mid, int end){
            for(int i = start; i<= end; i++){
                temp[i] = arr[i];
            }
            int part1 = start;
            int part2 = mid + 1;
            int index = start;
 
            while(part1<=mid && part2<=end){
                if(temp[part1] <= temp[part2]){
                    arr[index] = temp[part1];
                    part1++;
                }else{
                    arr[index] = temp[part2];
                    part2++;
                }
                index++;
            }
            for(int i = 0; i<= mid-part1; i++){
                arr[index+i] = temp[part1 + i];
            }
        }
 
        private void Print(int[] arr){
            foreach(var data in arr){
                Console.Write(data + " ");
            }
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            //new Solution1();
            //new Solution2();
            //new Solution3();
            new Solution4();
        }
    }
}
 
/*
if(test for the base case)
    return some base case value
else if(test for another base case)
    return some other base case value
//재귀조건 (the recursive case)
else 
    return (some work) and then (재귀호출)
 
 */