using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace zad2
{
//    Zadanie 2

//Zaprojektuj algorytm wykonujący łączenie dwóch ciągów niemalejących w jeden ciąg uporządkowany niemalejąco.

//Nie korzystaj z sortowania.Do rozwiązania dodaj analizę pesymistycznej złożoności swojego algorytmu, uzasadnij że algorytm się zakończy.
    class Program
    {
        static void PrzesunIndeks(List<int> c1, int i)
        {
            c1.Add(0);
            List<int> temp = new List<int>(c1);
            for (int j = i; j < c1.Count - 1; j++)
            {
                c1[j + 1] = temp[j];
            }
        }
        static void WypiszListe(List<int>L)
        {
            for (int i = 0; i < L.Count; i++)
            {
                Console.Write(L[i]+" ");
            }
        }
        static List<int> PolaczCiagi(List<int> c1, List<int> c2)
        {
            if (c1[c1.Count - 1] <= c2[0]) //jak ostatni wyraz c1 jest mniesjszy od pierwszego wyrazu c2 to po prostu dodaje c1 + c2
            {
                for (int i = 0; i < c2.Count; i++)
                {
                    c1.Add(c2[i]);
                }
                return c1;
            }
            if (c2[c2.Count - 1] <= c1[0])// jak ostatni wyraz c2 jest mniejszy od pierwszego wyrazu c1, to po prostu dodaje c2 + c1
            {
                for (int i = 0; i < c1.Count; i++)
                {
                    c2.Add(c1[i]);
                }
                return c2;
            }
            if (c1.Count>c2.Count) //jesli c1 jest dluzszy
            {
                Pesymistyczny(c1, c2);
                return c1;
            }
            Pesymistyczny(c2, c1); //jesli c2 jest dluzszy bądz sa rowne
            return c2;

        }
        static void Pesymistyczny(List<int>c1,List<int>c2)
        {
            int k=0;
            //sprawdzam zerowy wyraz, jak warunek spelniony to dalej w petli zaczynam od pierwszego zeby sie nie dublowaly
            if(c2[0]<=c1[0])
            {
                PrzesunIndeks(c1, 0);
                c1[0] = c2[0];
                k = 1;
            }
            int u = c2.Count;
            //sprawdzam ostatni wyraz, jak warunek spelniony to dalej w petli sprawdzam do przedostatniego zeby sie nie dublowaly
            if (c2[c2.Count-1]>=c1[c1.Count-1])
            {
                c1.Add(c2[c2.Count - 1]);
                u = c2.Count-1;
            }
            for (int i = k; i < u; i++)//petla od krotszego ciagu,  uwzgledniajaca pierwszy i ostatni wyraz zaleznie od poprzednich ifow
            {
                for (int j = 0; j < c1.Count-1; j++) //petla od dluzszego ciagu
                {
                    if (c2[i] >= c1[j]&&c2[i]<=c1[j+1]) //sprawdzam czy wyraz ciagu krotszego lezy miedzy dwoma wyrazami dluzszeho, jak tak to go wstawiam i przerywam
                    {
                        PrzesunIndeks(c1,j+1);
                        c1[j + 1] = c2[i];
                        break;
                    }
                }
            }
        }
        static void Main(string[] args)
        {
            List<int> c1 = new List<int>();
            List<int> c2 = new List<int>();
            c1.Add(13);
            c1.Add(15);
            c1.Add(31);
           c1.Add(66);
            c2.Add(1);
            c2.Add(20);
            c2.Add(45);
            c2.Add(66);




          List<int> wynik=new List<int>(  PolaczCiagi(c1, c2));
            WypiszListe(wynik);


            Console.ReadKey();
        }
    }
}