Merge sort: differenze tra le versioni

Versione delle 11:01, 20 mar 2008

Versione delle 06:07, 24 mar 2008

Riga 94:

mergesort(a, center+1, right)

merge(a, left, center, right)

==[[Java]]==

<source lang="java">

public class MergeSort {

public int[] mergeSort (int[]a, int l, int r) {

sort(a, l, r);

return a;

}

private void merge(int a[],int p, int q, int r) {

int n1 = q-p+1;

int n2 = r-q;

int L[] = new int[n1+2];

int R[] = new int[n2+2];

for(int i = 1; i <= n1; i++) {

L[i] = a[p+i-1];

}

for(int j = 1; j <= n2; j++) {

R[j] = a[q+j];

}

L[n1+1] = Integer.MAX_VALUE;

R[n2+1] = Integer.MAX_VALUE;

int i = 1;

int j = 1;

for(int k = p; k <= r; k++) {

if(L[i] < R[j]) {

a[k] = L[i];

i++;

}

else {

a[k] = R[j];

j++;

}

}

}

private void sort(int a[],int p, int r) {

if(p < r){

int q = (p+r)/2;

sort(a, p, q);

sort(a, q+1, r);

merge(a, p, q, r);

}

}

}

</source>

== Analisi delle prestazioni ==