Recursions3

using System;
using System.Collections.Generic;
using System.Linq;

namespace Recursion
{
    class Program
    {

        static int Fact(int n)
        {
            if (n == 0)
            {
                return 1;
            }
            return Fact(n - 1) * n;
        }

        static void PrintNumbers(int n)
        {
            if (n == 0)
            {
                return;
            }
            Console.Write($"{n} ");
            PrintNumbers(n - 1);
            Console.Write($"{n} ");
        }

        static void DrawTriangle(int n)
        {
            if (n == 0)
            {
                return;
            }
            Console.WriteLine(new string('*', n));
            DrawTriangle(n - 1);
            Console.WriteLine(new string('*', n));
        }

        static double Power(double a, int n)
        {
            if (n == 0)
            {
                return 1;
            }
            return a * Power(a, n - 1);
        }

        static double FastPower(double a, int n)
        {
            if (n == 0)
            {
                return 1;
            }
            else if (n % 2 == 0)
            {
                double x = FastPower(a, n / 2);
                return x * x;
            }
            else
            {
                return a * FastPower(a, n - 1);
            }
        }


        static int SumArr(int[] arr, int start)
        {
            if (start == arr.Length)
            {
                return 0;
            }
            return arr[start] + SumArr(arr, start + 1);
        }

        static int ProductArr(int[] arr, int start)
        {
            if (start == arr.Length)
            {
                return 1;
            }
            return arr[start] * ProductArr(arr, start + 1);
        }

        static int SumD(int n)
        {
            if (n < 10)
            {
                return n;
            }
            return n % 10 + SumD(n / 10);
        }

        static int DigitalRoot(int n)
        {
            if (n < 10)
            {
                return n;
            }
            return DigitalRoot(SumD(n));
        }

        static int gcd(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            return gcd(b, a % b);
        }


        static void HanoiTowers(int disks, char src, char mid, char dest)
        {
            if (disks == 1)
            {
                Console.WriteLine($"{src} -> {dest}");
                return;
            }
            HanoiTowers(disks - 1, src, dest, mid);
            HanoiTowers(1, src, mid, dest);
            HanoiTowers(disks - 1, mid, src, dest);
        }


        static int LinearSeach(int[] arr, int x)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == x)
                {
                    return i;
                }
            }
            return -1;
        }

        static int BinarySearch(int[] arr, int left, int right, int x)
        {
            if (right >= left)
            {
                int mid = left + (right - left) / 2;
                if (arr[mid] == x)
                {
                    return mid;
                }
                else if (x < arr[mid])
                {
                    Console.WriteLine("DOWN");
                    return BinarySearch(arr, left, mid - 1, x);
                }
                else
                {
                    Console.WriteLine("UP");
                    return BinarySearch(arr, mid + 1, right, x);
                }
            }
            return -1;
        }

        static int BinarySearch(int[] arr, int x)
        {
            return BinarySearch(arr, 0, arr.Length, x);
        }


        static int[] SortedMerge(int[] a, int[] b)
        {
            int[] c = new int[a.Length + b.Length];
            int ia = 0, ib = 0, ic = 0;
            while (ic < c.Length)
            {
                if (ia < a.Length && ib < b.Length)
                {
                    if (a[ia] < b[ib])
                    {
                        c[ic] = a[ia];
                        ia++;
                    }
                    else
                    {
                        c[ic] = b[ib];
                        ib++;
                    }
                }
                else if (ia < a.Length)
                {
                    c[ic] = a[ia];
                    ia++;
                }
                else
                {
                    c[ic] = b[ib];
                    ib++;
                }
                ic++;
            }
            return c;
        }

        static int[] MergeSort(int[] arr)
        {
            int[] left, right;

            int[] result = new int[arr.Length];

            if (arr.Length <= 1)
            {
                return arr;
            }
            int mid = arr.Length / 2;

            left = new int[mid];

            if (arr.Length % 2 == 0)
            {
                right = new int[mid];
            }
            else
            {
                right = new int[mid + 1];
            }

            for (int i = 0; i < mid; i++)
            {
                left[i] = arr[i];
            }

            for (int i = mid, j = 0; i < arr.Length; i++, j++)
            {
                right[j] = arr[i];
            }

            left = MergeSort(left);
            right = MergeSort(right);

            result = SortedMerge(left, right);

            return result;
        }

        static void Main(string[] args)
        {
            int[] a = { 1, 2434, 54, -34, 43, 544, 1054, 204, 78};
            int[] result = MergeSort(a);
            for (int i = 0; i < result.Length; i++)
            {
                Console.Write("{0} ", result[i]);
            }
        }
    }
}