|
A[i], A[i+1] := A[i+1], A[i]
if A[i] > A[i+1] > >
end
===Merge sort===
[[Merge sort]] the array using a constant time merge. Using <math>\Theta(\log n)</math> time, <math>\Theta(n^2)</math> processors and <math>\Theta(n^2)</math> work. It should have CREW [[PRAM]] complexity. The array <code>A</code> is sorted in an array of arrays <code>B</code>, with sentinels of negative and positive infinity.
Program mergesort
declare
n,m: integer,
A,N: array [0..n-1] of integer,
B: array [0..n,0..n+1] of integer
initially
n = 15 #
m = n #
<|| i : 0 <= i < n ::
A[i], N[i] = rand() % 100, 1 >
#
<|| i,j : 0 <= i < n and 0 <= j < n+2 ::
B[i,j] = -infi if j = 0 ~
A[i] if j = 1 ~
infi if j > 1 >
assign
<|| s : 0 <= s < m - 1 and s % 2 = 0 ::
<|| a,b : 0 <= a <= N[s] and 0 <= b <= N[s+1] ::
B[s / 2, a+b] := B[s, a]
if 1 <= a <= N[s] and B[s+1, b] < B[s, a] <= B[s+1, b+1] ||
B[s / 2, a+b] := B[s+1, b]
if 1 <= b <= N[s+1] and B[s, a] <= B[s+1, b] < B[s, a+1] > ||
N[s/2] := N[s] + N[s+1] > ||
N[(m-1)/2] := N[m-1] if m%2 = 1 ||
<|| a : m%2 = 1 and 1 <= a <= N[m-1] ::
B[(m-1)/2, a] := B[m-1, a] > ||
m := (m/2) + m%2 ||
<|| i : 0 <= i < n :: A[i] := B[0,i+1] >
end
Below is the same program rewritten to sort in-place. As you see, a bit more code is needed when you don't have the sentinels.
Program mergesort2
declare
n,m: integer,
A,S,N: array [0..n-1] of integer
initially
n = 20 #
m = n ||
<|| i : 0 <= i < n :: A[i], N[i], S[i] = rand() % 100, 1, i >
assign
<|| s : 0 <= s < m - 1 and s % 2 = 0 ::
<|| a,b : (a = 0 and b = 1) or (a = 1 and b = 0) ::
<|| sa : 0 <= sa < N[s+a] ::
A[S[s]+sa] := A[S[s+a]+sa]
if a = 0 and A[S[s+a]+sa] <= A[S[s+b]]
or a = 1 and A[S[s+a]+sa] < A[S[s+b]] ||
<|| sb : 0 < sb < N[s+b] ::
A[S[s]+sa+sb] := A[S[s+a]+sa]
if a = 0 and A[S[s+b]+sb-1] < A[S[s+a]+sa] <= A[S[s+b]+sb]
or a = 1 and A[S[s+b]+sb-1] <= A[S[s+a]+sa] < A[S[s+b]+sb] > ||
A[S[s]+sa+N[s+b]] := A[S[s+a]+sa]
if a = 0 and A[S[s+b]+N[s+b]-1] < A[S[s+a]+sa]
or a = 1 and A[S[s+b]+N[s+b]-1] <= A[S[s+a]+sa] > > ||
S[s/2] := S[s] ||
N[s/2] := N[s] + N[s+1] > ||
S[(m-1)/2], N[(m-1)/2] := S[m-1], N[m-1] if m%2 = 1 ||
m := m/2 + m%2
end
| 