#include <iostream> //Merge Sort

using namespace std;

const int POCET=10;

int merge(int p[],int q[],int n);

int main()

{

    int pocet=POCET;			// vstupni parametr - pocet prvku

	int pole[POCET];			// vstupní pole pro trideni

	int pole2[POCET];           // pro mergesort

	int k;

	cout<<"  Zadej prvky pole ke trideni: "<<endl<<endl;

	for (k=0; k<pocet; k++)	{cout<<"   pole["<<k<<"]= "; cin>>pole[k];}

    cout<<endl<<endl;

	merge(pole,pole2,pocet);

	cout<<"  Setridene pole (mergesort): "<<endl;

        	for (k=0; k<pocet; k++) {cout<<"  "<<pole2[k];}

    cout<<endl;



	return 0;

}





int merge(int p[], int q[], int n)

// trideni slucovanim - mergesort, algoritmus se lisi od

// standardniho postupu v tom,ze nerozdeluji tridene pole

// na useky stejne velikosti, nybrz delitkem je inverze mezi

// sousednimi prvky. Algoritmus se  diky tomu chova prirozeneji.

{

int * uk;	// tady pamatovat ukazatel na pole p

int * pom;	// pro vymenu ukazatelu

int i,j,k,m,l1,r1,l2,r2;

uk=p;

zac:m=0;

	while(m<n)

	{

		l1=m;r1=l1+1; 		// urcim meze 1.serazeneho useku

		while ((r1<n)&&(p[r1]>p[r1-1])) r1++;

		// a urcim, neni/li to cele pole

		if ((r1==n) &&  (l1==0))

		{

			if (pom==uk) // je to pole p?

			{

				for(k=0;k<n;k++)

					q[k]=p[k];

			}

			return 0; // hotovo

		}

		if (r1==n)

		{

			for (i=l1;i<r1;i++)

			{q[k]=p[i]; k++;}

			m=i+1;

		}

		else

		{

			l2=r1; r1--; r2=l2+1;

			while ((r2<n) && (p[r2]>p[r2-1])) r2++; // 2. usek

			r2--;

			i=l1; k=l1; j=l2;

			while ((i<=r1) && (j<=r2))

			{

				if (p[i] < p[j])

				{

					q[k]=p[i]; k++; i++;

				}

			    else

				{

			   	if (p[j] < p[i])

					{

				      	q[k]=p[j]; j++; k++;

			        }

				}

			}

         if (i>r1)

			{

				while (j<=r2)

				{ q[k]=p[j]; j++;  k++; }

			}

         else

			if (j>r2)

			{

				while(i<=r1)

				{ q[k]=p[i]; i++; k++; }

			}

		 m=r2+1;

		}

	}

	pom=p;

	p=q;

	q=pom;

	goto zac;

}