SELECTION SORT

int minpos(sarray data, int first, int last) 
   int cnt, min
 
   min := first
   for cnt $\in$ [first + 1 ... last]    $\rightarrow$  
      if data[cnt] < data[min]    $\rightarrow$  
      min := cnt 
   rof 
   return    min 
end    minpos 
 
 
void  selectsort(sarray  data, int length) 
   int cnt, pos
 
   for cnt $\in$ [0 .. length - 2]     $\rightarrow$ 
      pos := minpos(data, cnt, length - 1)
      data[cnt]  $\leftrightarrow$  data[pos] 
   rof 
end    selectsort

INSERTION SORT

void insort(sarray data, int length) 
   int cnt1, cnt2, tmp
 
   for cnt1 $\in$ [1 ... length - 1]    $\rightarrow$ 
      cnt2 := cnt1
      tmp := data[cnt1]
      do (cnt2 > 0) and (tmp < data[cnt2 - 1])    $\rightarrow$  
         data[cnt2] := data[cnt2 - 1]
         cnt2 := cnt2 -1 
      od
      data[cnt2] := tmp
   rof 
end   insort

QUICKSORT I

int partition(sarray data, int first, int last) 
   int m, k, pivot
 
   pivot := data[first]
   m := first
   for k  $\in$ [first + 1 ... last]    $\rightarrow$ 
      if data[k] <= pivot    $\rightarrow$ 
         m := m + 1
         data[m]  $\leftrightarrow$  data[k] 
      fi 
   rof
   data[m]  $\leftrightarrow$  data[first]
   return   m 
end partition

void qsort(sarray data, int first, int last) 
   int m 
 
   if first < last    $\rightarrow$ 
      m := partition(data, first, last)
      qsort(data, first, m - 1)
      qsort(data, m + 1, last)
   fi 
end qsort
 
 
void  quicksort(sarray data, int length) 
 
   qsort(data, 0, length - 1)
end   quicksort

QUICKSORT II

int partition_ran(sarray data, int first, int last)  
   int k, h, m, pivot
   h  :=  randint(first, last);     pivot  :=   L[h]
   L[h] $\leftrightarrow$ L[first]
   m  :=  first 
   for k $\in$ [first+1..last]     $\rightarrow$  
      if  L[k]  $\leq$  pivot    $\rightarrow$  
         m++;       L[k] $\leftrightarrow$ L[m]  
      fi 
   rof
   L[first]  $\leftrightarrow~$ L[m] 
   return m  
end partition_ran

void qsort_ran(sarray data, int a, int b)  
   if a  < b    $\rightarrow$  
      m  :=   partition(data, a, b) 
      qsort_ran(data, a,  m-1) 
      qsort_ran(data, m+1,  b)  
   fi 
end qsort_ran 
  
 
void  quicksort_rand(sarray data, int length) 
 
   qsort_ran(data, 0, length - 1)
end   quicksort_rand

MERGE SORT

void mergesort(int a, int b, ltype&  L)  
   int m 
   if a  <  b    $\rightarrow$  
      m  :=  (a+b) div 2 
      mergesort(a, m, L) 
      mergesort(m+1, b, L) 
      merge(a, m, b, L)  
   fi  
end mergesort 
 
ltype copy(nt a, int b, ltype L)  
   int i
   ltype lnew
   for i  $\in$ [a..b]    $\rightarrow$   lnew(i) := L(i)   rof
      lnew[b+1]  :=  $\infty$ 
   return lnew  
end copy

void merge(int a, int b, int c, ltype& L)  
   ltype l1, l2
   int ind1, ind2, ind 
   l1  := copy(a, b, L);       l2 := copy(b+1, c, L) 
   ind1  :=  a;    ind2  :=  b+1;    ind  :=  a 
   do ind  $\leq$  c    $\rightarrow$  
      if l1[ind1]  $\leq$  l2[ind2]    $\rightarrow$  
         L[ind]  :=  l1[ind1];     ind1++  
      |  l1[ind1]  >  l2[ind2]    $\rightarrow$  
         L[ind]  :=  l2[ind2];    ind2++  
      fi 
      ind++  
   od  
end merge