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 ligiloj 

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

Kategorio:Algoritmoj de ordigo

no:Sorteringsalgoritme#Flettesortering