// Algorytm Merg-sort ma na celu scalenie dwoch posortowanych tablic

// optymistyczna złożoność jak tablice sa 12345 678910

// pesymistyczna złożoność jak sa pomieszane 13579 246810

public

class Program {

public static void main(String[] args)

{

int tab1[]={4};

int tab2[]={5};

int tab[] = {8,7,6,5,4,3,2,1,45,23,32,68,76,12,13,8};

tab = Mergesort(tab,0,tab.length-1);

//tab = Scalaj(tab1,tab2);

for(int l = 0; l<tab.length; l++)

{

System.out.print(tab[l]+" ");

}

}

public static int[] Scalaj(int []tab1,int []tab2){

int tab3[]=new int[tab1.length + tab2.length];

int i=0,j=0,k=0;

while(i<tab1.length && j< tab2.length){ // jesli indeksy (i,j) sa w tablicach

if(tab1[i] < tab2[j]){ // jesli element z tab1 jest mniejszy od tego z tab

tab3[k] = tab1[i]; // to do nowej tablicy wrzuc element tab1

i++;

}else{

tab3[k] = tab2[j]; // jesli odwrotnie to wrzuc element tab2

j++;

}

k++;

}

if(j==tab2.length){ // jesli indeks j wyjdzie po za tablice tab2

for(int l = i; l < tab1.length;l++){// to

tab3[k]=tab1[l]; // przwpepisujemy elementy do nowej tablicy elementy z tablicy tab1

k++;

}

}else{ // w przeciwnym wypadku (indeks i wyjdzie po za tablice tab1)

for(int n = j; n < tab2.length;n++){

tab3[k]=tab2[n]; // to przwpepisujemy elementy do nowej tablicy elementy z tablicy tab2

k++;

}

}

return tab3;

}

public static int[] Mergesort(int[] tab3,int p,int r){

int tab1[] = new int[1];

int tab2[];

if(p < r){ //sprawdza czy tsblica czy tablica nie jest równa jeden

int q = (p+r)/2; //srodek tablicy

tab1 = Mergesort(tab3,p,q); //dzieli pierwsza czesc tablcy na pol

tab2 = Mergesort(tab3,q+1,r); //dzieli druga czesc tablicy na pol

tab3 = Scalaj(tab1,tab2); //uruchomienie scalania dla tab1 i tab2

}else{

tab1[0] = tab3[p]; //z tabicy jednoelementowej przepisuje na poczotek tab1

tab3=tab1; //

}

return tab3;

//algorytm Insertion-Sort polega na wybraniu i wstawienu ardumentu w odpowiednie miejsce,

//a dokładniej rzecz biorąc, na przesunieciu argumentu w tablicy na takie miejsce ,

//by ciag tych argumentów był ustawiany wkolejności rosnącej

// algorytm ten najpeliej działa dla niewielkiej ilości argumentów w tablicy

//najktotszy czas działnia (optymistyczny n)będzie dla wejśćowej tablicy z elementami juz posortowanymi

//najdłuższ czas działania (pesymityczny n2)będzie dla wejśćowej tablicy posotrowanij odwrotnie

//operacja dominująca porównywanie elementów

int tab[] = {3,6,4,2,7,5,6,78,9,3,7,98,};

int licznik,pom;

for(int i = 1; i < tab.length; i++)

{

licznik = i;

pom = tab[i];

while(licznik>0 && tab[licznik-1] > pom){ // jezeli licnik jest wiekszu od zera i poprzednie wyrazenie w tablicy jest wieksze od liczb sparwdzanej

tab[licznik] = tab[licznik-1]; //to nastepuje zamata tych liczb

licznik--; // cofanie indeksu

}

tab[licznik] = pom; //zapisuje lioczbe sprawdzana w miejscu przeznaczenia

}

for(int i = 0; i<tab.length; i++)

{

System.out.print(tab[i]+" ");

}*/

} }