Mergesort iteracyjny

Witam!
Przyszedł czas w mojej nauce na implementację Merge sorta iteracyjnie, co też uczyniłem, niestety Bubblesort działa nawet szybciej od tego, sortuje dobrze, ale nie wiem czemu tak wolno;/

void mergesort(int a[], int lewy, int prawy, int pom[])
{
	int start, end, end2,i,start2,temp;
	bool koniec=true;
	while(koniec)
	{
		i=lewy;
		while(i<=prawy&&koniec)
		{
			start=i;
			temp=i;
			i++;
			while(a[i]>=a[temp]&&i<=prawy)
			{
				temp=i;
				i++;
			}
			end=temp;
			if(end-start==prawy-lewy)
				koniec=false;
			else if(i<=prawy)
			{
				start2=i;
				temp=i;
				i++;
				while(a[i]>a[temp]&&i<=prawy)
				{
					temp=i;
					i++;
				}
				end2=temp;
				scal(a,start,end,start2,end2,pom);
			}
		}
	}
}
void scal(int a[], int start1, int end1, int start2, int end2, int pom[])
{
	// cout<<"start1 = "<<start1<<" end1 = "<<end1<<" start2 = "<<start2<<" end2 = "<<end2<<endl;
	// system("pause");
	for(int i=start1;i<=end2;i++)
	{
		pom[i]=a[i];
	}
	int i,j,poz;
	i=start1;
	j=start2;
	poz=start1;
	while(i<=end1&&j<=end2)
	{
		if(pom[i]<pom[j])
		{
			a[poz]=pom[i];
			i++;
		}
		else
		{
			a[poz]=pom[j];
			j++;
		}
		poz++;
	}
	while(i<=end1)
	{
		a[poz]=pom[i];
		i++;
		poz++;
	}
	while(j<=end2)
	{
		a[poz]=pom[j];
		j++;
		poz++;
	}
}
 

Ponieważ masz zbędne kopiowanie całej tablicy log(N) razy.
Poza tym jeżeli jeden algorytm ma czas:
O(N²) czyli np: XN²
zaś drugi ma czas:
O(Nlog(N)) czyli np: YNlog(N)
to przeważnie jest tak że Y>X
Zaś z powyższego wynika że drugi algorytm będzie lepszy ale dopiero przy wystarczająco dużym N.

Czyli tą tablicę skopiować pomiędzy

	while(koniec)
	{
         //kopiowanie
		i=lewy;
		while(i<=prawy&&koniec)
		{ 

?

Nie, chodzi o przekazywanie a oraz pom poprzez wskaźniki oraz swap-owanie wskaźników.

Przepisałem to kopiowanie, wiem że to nic nie zmienia ale też działa. A jak inaczej to rozwiązać, a i pom są dynamiczne, w zasadzie każde moje sortowanie jest na tej zasadzie. Dodam jeszcze że jeżeli zwiększam zasięg losowania liczb do tablicy to dal tych samych rozmiarów sortuje się coraz szybciej, także chociaż to działa.

na początku mergesort robisz:
int *tb[2]={a,pom};
bool transfer=true;
do scal przekazujesz to tb oraz transfer po obróbki całego poziomu zmieniasz transfer=!transfer;
scal scala z tb[!transfer] do tb[transfer].
ma końcu mergesort jeżeli (!transfer) to kopiujesz z pom do a.

O dziękuję, już to piszę. Wywaliłem jednego whila jeszcze, nic to jednak do szybkości nie dało.