MergeSort

Psydocode

MergeSort(H,r,l)

 if l < r then
   m := l + r / 2  (untere Schranke)
   MergeSort( H , l , m )
   MergeSort( H , m + 1 , r )
   Merge( H , l, m, r )

Merge(H,l,m,r)

j := l
k := m + 1
for i := l to r do
  if j > m then
    B[i] = A[k];
    k := k + 1
  if k > r then
    B[i] = A[j];
    j := j + 1
  if H[j] < H[k] then
    B[i] = A[j];
    j := j + 1
  else
    B[i] = A[k];
    k := k + 1
 Speicher für B wieder freigeben