It means business

 AS-ArtificialSort 
 QS - QuickSort z InsertionSortom
 
 read    - read data from array
 write   - write data to array
 compare - compare data
 režija  - ostalo
 ------------------------------------------------------------------------------------------------
 NumberOfRec = 30.000.000  Data = Rnd(-10000000, 10000000)
 AS režija 1425729604 read 1457520705 write 331048566 compare 1124275862 Elapsed time = 14766 ms
 QS režija 1236597458 read 1163307478 write 392699278 compare  841307557 Elapsed time = 13937 ms
 
 NumberOfRec = 30.000.000  Data = Rnd(-1000000, 1000000)
 AS režija 1126225365 read 1318397267 write 289698392 compare 996161830 Elapsed time = 11875 ms
 QS režija 1129982923 read 1138995189 write 355461726 compare 804815548 Elapsed time = 12594 ms
  
 NumberOfRec = 30.000.000  Data = Rnd(-100000, 100000)
 AS režija  873085958 read 1082705771 write 245138876 compare 806880105 Elapsed time =  9859 ms
 QS režija 1062647478 read 1136889289 write 364675890 compare 764056912 Elapsed time = 11500 ms
 
 NumberOfRec = 30.000.000  Data = Rnd(-10000, 10000)
 AS režija  697437376 read  866605407 write 199708736 compare 636823126 Elapsed time =  7859 ms
 QS režija 1089829551 read 1193201489 write 407584329 compare 773708870 Elapsed time = 10828 ms
 -----------------------------------------------------------------------------------------------
 NumberOfRec = 10.000.000  Data = Rnd(-10000000, 10000000)
 AS režija 456338774  read 456422483  write 107896370 compare 352749508  Elapsed time = 4657 ms
 QS režija 403411431  read 368796252  write 126211927 compare 269878448  Elapsed time = 4438 ms
 
 NumberOfRec = 10.000.000  Data = Rnd(-1000000, 1000000)
 AS režija 425885693  read 440130660  write  96803342 compare 336866681  Elapsed time = 4265 ms
 QS režija 385391118  read 368389086  write 115959022 compare 268894251  Elapsed time = 4125 ms
 
 NumberOfRec = 10.000.000  Data = Rnd(-100000, 100000)
 AS režija 295435485  read 361532063  write  81886746 compare 269054474  Elapsed time = 3468 ms
 QS režija 335738276  read 349297998  write 109628067 compare 239551295  Elapsed time = 3687 ms
 
 NumberOfRec = 10.000.000  Data = Rnd(-10000, 10000)
 AS režija 240164344  read 295350957  write  65730146 compare 219548985  Elapsed time = 2609 ms
 QS režija 331276927  read 357870840  write 121238757 compare 232952747  Elapsed time = 3422 ms
 -----------------------------------------------------------------------------------------------
 NumberOfRec = 1.000.000  Data = Rnd(-1000000, 1000000)
 AS režija 40119064   read 38587749   write  9324928  compare 29748757   Elapsed time = 406 ms
 QS režija 35427886   read 31128851   write 11085581  compare 22806218   Elapsed time = 359 ms
 
 NumberOfRec = 1.000.000  Data = Rnd(-100000, 100000)
 AS režija 37755843   read 37651281   write  8133830  compare 28866677   Elapsed time = 359 ms
 QS režija 32871091   read 30442451   write 10136824  compare 21949091   Elapsed time = 344 ms
 
 NumberOfRec = 1.000.000  Data = Rnd(-10000, 10000)
 AS režija 24433781   read 29487320   write 6632420   compare 21795754   Elapsed time = 265 ms
 QS režija 29150172   read 29704019   write 9343026   compare 20345168   Elapsed time = 297 ms
 
 NumberOfRec = 1.000.000  Data = Rnd(-1000, 1000)
 AS režija 19166166   read 23103959   write  4992466  compare 17104124   Elapsed time = 187 ms
 QS režija 28600020   read 30459367   write 10512159  compare 19579921   Elapsed time = 265 ms
 -----------------------------------------------------------------------------------------------
 

#include <cstdio>
#include <cstdlib>
#include <windows.h>
#include <algorithm>


class Int {
	int data;
	static double countCreate;
	static double countAssign;
	static double countConvert;
	static double countCompare;

public:
	inline Int() {++countCreate;}
	inline Int(int d) : data(d) {++countCreate;}
	inline Int(const Int& i) : data(i.data) {++countAssign;}
	inline const Int& operator=(const Int& i) {++countAssign; data = i.data; return *this;}
	inline const Int& operator=(int i) {++countAssign; data = i; return *this;}
	friend inline bool operator== (const Int& i1, const Int& i2) {return (i1.data == i1.data);}
	friend inline bool operator< (const Int& i1, const Int& i2) {++countCompare; return i1.data < i2.data;}
	friend inline bool operator<= (const Int& i1, const Int& i2) {++countCompare; return i1.data <= i2.data;}
	friend inline bool operator!= (const Int& i1, const Int& i2) {return !(i2 == i1);}
	friend inline bool operator> (const Int& i1, const Int& i2) {return (i2 < i1);}
	friend inline bool operator>= (const Int& i1, const Int& i2) {return (i2 <= i1);}
	inline operator int& () {++countConvert; return data;}
	inline operator int () const {++countConvert; return data;}
	
	static void printStats() {
		printf("%10.0f + %10.0f + %10.0f + %10.0f = %10.0f\n", 
			countCreate, countAssign, countConvert, countCompare, 
				countCreate+countAssign+countConvert+countCompare);
	}
	
	static void resetStats() {
		countCreate = 0;
		countAssign = 0;
		countConvert = 0;
		countCompare = 0;
	}
};


double Int::countCreate = 0;
double Int::countAssign = 0;
double Int::countConvert = 0;
double Int::countCompare = 0;


static const int NumberOfRec = 50000000;
static const int buffersize = 2000000;
int* levi;
int* desni;
Int* array;
Int* arrayCpy;


int Rnd(int x1, int x2) {
    int x = x2 - x1 + 1;
    int m = (rand() % x) + x1;    
    int n = (rand() % x) + x1;    
    m = (32000*m + n) % x;
    return m;     
}


// sprememba v definiciji funkcije
void ArtificialSort(Int array[], int nor) { 
	// spremembe v definiciji spremenljivk
    int index = 0; int i = 0; int j = 0; 
    int left = 0; int right = 0; int sinistra = 0; Int meja = 0;
    Int temp1 = 0; Int temp2 = 0; Int temp = 0;
	
	// od tu naprej pa nespremenjena koda
    left = 0; right = nor-1;

    while (left < right){
        if (array[left] > array[right]) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        } else {
            break;
        }
        left++; right--;
    }

    index = 0; levi[index] = 0; desni[index] = nor-1;

    i = index;
    while ( index >= i ) {
        left = levi[i]; right = desni[i];
        if ( right-left < 11 ) {
            sinistra = left;
            temp1 = array[right]; temp2 = array[sinistra];
            if ( temp2 > temp1 ) {
                goto labelcritticall3;
            }
            sinistra++;
            labelcritticall15:;
            while ( sinistra < right ) {
                temp2 = array[sinistra];
                if ( temp2 > temp1 ) {
                    array[right] = temp2; array[sinistra] = temp1; 
                    temp1 = temp2;
                }
                sinistra++;
            }
            temp1 = temp2;
            sinistra = left; temp2 = array[sinistra];
            right--;
            if ( temp2 > temp1 ) {
                labelcritticall3:;
                array[right] = temp2; array[sinistra] = temp1;
                temp1 = temp2;
            }
            sinistra++;
            if ( sinistra < right ) {
                temp2 = array[sinistra];
                if ( temp2 > temp1 ) goto labelcritticall3;
                sinistra++;
                goto labelcritticall15;
            }
        } else {
            for ( j = left; j < right; j++ ) {
                if ( array[j] > array[j+1] ) {
                    meja = ( array[j] + array[j+1] + 1 ) / 2;
                    if ( array[ (left + right) / 2 ] > meja ) meja = array[ (left + right) / 2 ];
                    sinistra = left;
                    while ( true ) {
                        while ( array[sinistra] < meja ) sinistra++;
                        while ( array[right] >= meja ) right--;
                        if ( sinistra > right ) break;
                        temp2 = array[right];
                        array[right] = array[sinistra];
                        array[sinistra] = temp2;
                        right--;
                    }
                    temp = desni[i];
                    if ( i > 0 ) desni[i] = right; else { levi[++index] = left; desni[index++] = right;}
                    right++;
                    if ( i != 0 ) {levi[--i] = right; desni[i] = temp; goto labelcritticall5;}
                    levi[index] = right;
                    desni[index] = temp;
                    break;
                }
            }
        }
        i++;
        labelcritticall5:;
    }

}


int main() {
	try {
		array = new Int[NumberOfRec];
		arrayCpy = new Int[NumberOfRec];
		levi = new int[buffersize];
		desni = new int[buffersize];
		
		printf ("\n");
		printf (" ArtificialSort\n");
		printf ("\n");
		printf (" Creating array of random numbers ...\n");
		
		for (int i=0; i<NumberOfRec; i++) {
			array[i] = Rnd(1,10000000)-Rnd(1,10000000);
		}
		
		printf (" copy\n");
		std::copy(array, array+NumberOfRec, arrayCpy);
		
		Int::resetStats();
		printf ("\n Sorting (asort) ...\n");
		int timtim = GetTickCount();
		ArtificialSort(array, NumberOfRec);
		printf ("\n Elapsed time = %d ms\n", (int)GetTickCount()-timtim);
		Int::printStats();
		
		Int::resetStats();
		printf ("\n Sorting (qsort) ...\n");
		timtim = GetTickCount();
		std::sort(arrayCpy, arrayCpy + NumberOfRec);
		printf ("\n Elapsed time = %d ms\n", (int)GetTickCount()-timtim);
		Int::printStats();
		
		delete levi;
		delete desni;
		delete array;
		delete arrayCpy;
		
		return 0;
	} catch(...) {
		printf("oops\n");
	}
}

 nekaj ArtificialSort kode:                      operacije
 -----------------------------------------------------------------------
       sinistra = left;                          režija++;
       while ( true ) {
           while ( array[sinistra] < meja ) {    read++; compare++;
             sinistra++;                         režija++;
           }
           while ( array[right] >= meja ) {      read++; compare++;
             right--;                            režija++;
           }
           if ( sinistra > right ) break;        režija++;
 
           temp2 = array[right];                 read++;
           array[right] = array[sinistra];       read++; write++;
           array[sinistra] = temp2;              write++;
           right--;                              režija++;
       }
       temp = desni[i];                          režija++;
       if ( i > 0 ) {                            režija++;
           desni[i] = right;                     režija++;
       } else {
           levi[++index] = left;                 režija+=2;
           desni[index++] = right;               režija+=2;
       }
       right++;                                  režija++;
 -----------------------------------------------------------------------
 
 
 nekaj QuickSort kode:                           operacije
 -----------------------------------------------------------------------
       down = first;                             režija++;
       up = last;                                režija++;
       for (;;)
       {
         do
         {
           ++down;                               režija++;
         } while (pivot > This[down]);           read++; compare++;
 
         do
         {
           --up;                                 režija++;
         } while (This[up] > pivot);             read++; compare++;
 
         if (up > down)                          režija++;
         {
           int temp;
           temp = This[down];                    read++;
           This[down]= This[up];                 read++; write++;
           This[up] = temp;                      write++;
         }
         else
           break;
       }
     }
     {
       uint32 len1;
       uint32 len2;
       len1 = up - first + 1;                    režija+=3;
       len2 = last - up;                         režija+=2;
       if (len1 >= len2)
       {
         first_stack[stack_pointer] = first;     režija++;
         last_stack[stack_pointer++] = up;       režija+=2;
 
         first = up + 1;                         režija+=2;
       }
 -----------------------------------------------------------------------
 

nekaj ArtificialSort kode:

nekaj QuickSort kode:

Ali en pohaca 2000 milijonov al 2010 milijonov primerjanj je irrelevantno. Relevantno je koliko je vse skup trajalo, ker tut vsa primerjanja med sabo niso ekvivalentna - cache, paralelnost kode, težko predvidljivo brenchanje etc - bistveno preveč parametrov vpliva na hitrost izvajanja kode, da bi se splačalo gledat EN PARAMETER -> skupno število enostavnih operacij. Ocena zahtevnosti je relevantna šele ko hočeš videt kako čas narašča s povečevanjem dataseta.

Čisto nič drugega nas ne briga, kot realna hitrost algoritma - ponavadi.

Torej se meriti ne da?

meja = ( array[j] + array[j+1] + 1 ) / 2;