Răspuns:
void sort(int *v, int n){
if(n == 1){ // Daca vectorul are un singur element este deja sortat
return;
}
int np2 = n / 2;//Impartim vectorul in 2 vectori mai mici
sort(v, np2); // Ii sortam
sort(v + np2, n - np2);
//Si apoi interclasam
{
// Cu memorie auxiliara
int *aux = new int[n];
int i = 0, j = np2, k = 0;
while(i < np2 && j < n){
if(v[i] < v[j]){
aux[k++] = v[i++];
}else {
aux[k++] = v[j++];
}
}
while(i < np2)
aux[k++] = v[i++];
while(j < n)
aux[k++] = v[j++];
for(i = 0; i < k; i++)
v[i] = aux[i];
delete aux;
}
}
Explicație:
Acest algoritm se numeste Merge Sort si are complexitatea [tex]O(n log\:n)[/tex]. Poate e mai greu de inteles decat alti algoritmi ca Bubble Sort, Insertion/Selection Sort dar este mult mai eficient pe vectori foarte mari
