Ordinare un vettore con costo N log2 (N)

Ordinare un vettore è un' operazione che solitamente (con algoritmi tra i quali c'è il Bubble Sort) ha un costo N².
Con Merge Sort questo no è un problema.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

void mergesort(int* V, int g){ if(g == 1) return; int k = (g /2); int s2 = g-k; int V1 [k]; assert(V1!=NULL); int V2 [s2]; assert(V2!=NULL); for ( i = 0; i < k ; i++) V1[ i ] = V[ i ]; for ( i = 0; i < s2 ; i++){ V2[i] = V[k+i]; } merge(V1,k); merge(V2,s2); int i1,i2; i1=i2 =0; while (i1 <k && i2<s2){ if (V1[i1] <= V2[i2]) { V[i1+i2] = V1[i1]; i1++; } else{ V[i1+i2]=V2[i2]; i2++; }} while (i1 < k) { V[i1+i2] = V1[i1]; i1++; } while (i2 <s2) { V[i1+i2] = V2[i2]; i2++; } return; }