Kunfanda ordigo

La algoritmo pri Kunfanda Ordigo (Merge sort en la angla) estas stabila eksterordiga algoritmo bazita sur la tekniko dividu kaj venkos. Ĝia komplekso estas O(n log n).

Priskribo

Estis prilaborita je 1945 far John von Neumann.

Superrigarde, la algoritmo temas pri dividi je du samgrandaj partoj la ordigotan vektoron, ordigi ĉiun parton aparte, kaj poste kunigi ambaŭ partojn ĝustorde en nur unu ordigitan vektoron.

Jene oni montras la algoritmon (atentu ke ne konsideras specialajn okazojn kiel vakuan vektoron, ktp; serioza realigo devas konsideri tiajn okazojn):

function mergesort(array A[0..n])
begin
  array A1 := mergesort(A[0..(int(n / 2))])
  array A2 := mergesort(A[int(1 + n / 2)..n])
  return merge(A1, A2)
end

function merge(array A1[0..n1], array A2[0..n2])
begin
  integer p1 := 0
  integer p2 := 0
  array R[0..(n1 + n2 + 1)]
  while (p1 <= n1 or p2 <= n2):
    if (p1 <= n1 and A1[p1] <= A2[p2]):
      R[p1 + p2] := A1[p1]
      p1 := p1 + 1
    if (p2 <= n2 and A1[p1] > A2[p2]):
      R[p1 + p2] := A2[p2]
      p2 := p2 + 1
  return R
end

Eksteraj ligoj

• Animacio de Algoritmo pri kunfanda ordigo - Merge Sort - Ĝava realigo.