codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# merge sort BEGIN { for (i=0; i<=20; i++) tester(i) tester(1000) } function tester(i) { genid(x,i); sort(x,i); check(x,i); clear(x) gensort(x,i); sort(x,i); check(x,i); clear(x) genrev(x,i); sort(x,i); check(x,i); clear(x) genrand(x,i); sort(x,i); check(x,i); clear(x) } function genid(x,n, i) { for (i=1; i<=n; i++) x[i] = 1 } function gensort(x,n, i) { for (i=1; i<=n; i++) x[i] = i } function genrev(x,n, i) { for (i=1; i<=n; i++) x[i] = n + 1 - i } function genrand(x,n, i) { for (i=1; i<=n; i++) x[i] = int(n * rand()) } function check(x,n, i) { for (i=1; i<n; i++) if (x[i+1]+0 < x[i]+0) { printf "error in sort" exit } } function clear(x, i) { for (i in x) delete x[i] } function merge(A,left,middle,right, B,i,j,k) { i = left; j = middle + 1 while (i <= middle && j <= right) if (A[i] <= A[j]) B[++k] = A[i++] else B[++k] = A[j++] while (i <= middle) B[++k] = A[i++] while (j <= right) B[++k] = A[j++] for (k = left; k <= right; k++) { A[k] = B[k]; delete B[k] } } function mergesort(A,left,right, middle) { if (left < right) { middle = int((left + right) / 2) mergesort(A, left, middle) mergesort(A, middle + 1, right) merge(A, left, middle, right) } } function sort(A,n) { mergesort(A, 1, n) } function sort(A,n, l1,l2,u1,u2,k,g,B) { for (g = 1; g < n; g *= 2) { k = 0 for (l1 = 1; l1 + g <= n; l1 = u2 + 1) { l2 = l1 + g; u1 = l2 - 1 u2 = l2 + g - 1; if (u2 > n) u2 = n while (l1 <= u1 && l2 <= u2) if (A[l1] <= A[l2]) B[++k] = A[l1++] else B[++k] = A[l2++] while (l1 <= u1) B[++k] = A[l1++] while (l2 <= u2) B[++k] = A[l2++] } while (k < n) B[++k] = A[l1++] for (k = 1; k <= n; k++) A[k] = B[k] } }
Private
[
?
]
Run code
Submit