sortowanie merge sort bez rekurencji (szybkie sortowanie)

Question

Witam dzisiaj przedstawiam wam merge sort bez rekurencji

 

musisz wywołać metodę wstepMergeSort

private static int[] copy;
	
public static void wstepMergeSort(int tab[], int lewy, int prawy) {
	copy = new int[prawy+2];
	int rozmiar = 2;
	int wskaznik = lewy;
	while(true) {
		int lewy1 = wskaznik;
		int prawy2 = wskaznik + (rozmiar-1);
		int prawy1 = wskaznik + (rozmiar-1)/2;
		int lewy2 = prawy1+1;
			
		if(prawy1 > prawy) {
			prawy1 = prawy;
		}
		if(lewy2 > prawy) {
			lewy2 = prawy;
		}
		if(prawy2 > prawy) {
			prawy2 = prawy;
		}
			
		startSortujIPowiekszaj(tab, lewy1, prawy1, lewy2, prawy2);
			
			
		wskaznik = prawy2 + 1;
			
		if(wskaznik>prawy) {	
			wskaznik = lewy;
				
			if(rozmiar>prawy) {
				break;
			}
				
			rozmiar *= 2;
				
		}
	}
}
	
public static void startMergeSort(int tab[], int lewy1, int prawy1, int lewy2, int prawy2) {
	int wLG = lewy1;
	int wPG = lewy2;
	int wskaznik = lewy1;
		
	while(true) {
		if(wLG > prawy1) {
			while(wPG <= prawy2) {
				copy[wskaznik] = tab[wPG];
				wskaznik++;
				wPG++;
			}
			break;
		}
		else if(wPG > prawy2) {
			while(wLG <= prawy1) {
				copy[wskaznik] = tab[wLG];
				wskaznik++;
				wLG++;
			}
			break;
		}
		else if(tab[wLG]<tab[wPG]) {
			copy[wskaznik] = tab[wLG];
			wLG++;
			wskaznik++;
		}
		else if(tab[wLG]>=tab[wPG]) {
			copy[wskaznik] = tab[wPG];
			wPG++;
			wskaznik++;
		}
	}
		
	for(int i=lewy1; i<=prawy2; i++) {
		tab[i] = copy[i];
	}
}

 

Answer 1

Na oko (kod trochę mało czytelny :( ) wygląda jak zwykły merge sort?

https://asciinema.org/a/LtKu152vovBltlgcbdXILRoXB

i pamięci ram

Z definicji ma gorsze zużycie ramu od quicksorta, bo alokuje drugą tablicę o tym samym rozmiarze - a quicksort korzysta tylko ze stosu do głębokości log N.

Comments

chciałem tylko sprawdzić czy ktoś zwróci uwagę. wiec szybko poprawiłem post że tylko moc obliczeniowy jest optymalizowane.

---

trochę jest podobny do merge sort tylko że bez rekurencji.