/*   Sortarea prin  interclasare folosind metoda DIVIDE & IMPERA
      Se considera un vector a de dimensiune n. Sa se sorteze crescator
      vectorul prin metoda interclasarii/
  Vectorul dat se imparte in 2 vectori, care odata sortati se interclaseaza.
	Se vor utiliza 3 functii:
  - o functie sort care va sorta un vector de maxim 2 elemente
  - o functie intercl care interclaseaza rezultatele
  - o functie divimp care implementeaza strategia tehnicii D&I
*/
#include <stdio.h>
#include <conio.h>
int a[10],n;
void sort(int p, int q, int a[10])
	{
  	int aux;
    if (a[p]>a[q])
    	{ aux=a[p];
        a[p]=a[q];
        a[q]=aux;
      }
  }
void intercl(int p, int q, int m, int a[10])
	{ int b[10],i,j,k;
  	i=p;j=m+1,k=1;
    while (i<=m && j<=q)
    	if(a[i]<=a[j])
      	{b[k]=a[i];
        i++;
        k++;
        }
      else
      	{ b[k]=a[j];
        j++;
        k++;
        }
   	if (i<=m)
 			for(j=i;j<=m;j++)
			{
      b[k]=a[j];
    	k++;
    	}
 		 else
 			for(i=j;i<=q;i++)
    	{
      b[k]=a[i];
      k++;
    }
 		k=1;
 		for(i=p;i<=q;i++)
 			{ a[i]=b[k];
  			k++;
  		}
	}
void divimp(int p, int q, int a[10])
	{
	  int m;
    if ((q-p)<=1) sort(p,q,a);
    	else
      	{ m=(p+q)/2;
        	divimp(p,m,a);
          divimp(m+1,q,a);
          intercl(p,q,m,a);
         }
  }

void main(void)
{
 clrscr();
 int i;
 printf("nr elemente pentru a =");scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
   printf("a[%d]=",i);scanf("%d",&a[i]);
 }
 divimp(1,n,a);
 for(i=1;i<=n;i++)
   printf("%d\t",a[i]);
 printf("\n");
 getch();
 }