Sameiningarröðun

Sameiningarröðun (e. mergesort) er tegund röðunaralgríms sem hefur tímaflækjuna O(n log n). Algrímið er er stöðugt sem þýðir að jafngild stök koma koma fyrir í sömu röð fyrir og eftir röðun. Þetta er tegund deili- og drottnunarreiknirits og var fyrst útfært af John von Neumann árið 1945. 

Sameiningarröðun
Sameiningarröðun nýtir þann eiginleika hversu auðvelt það er að sameina tvo raðaða lista. Röðunin byrjar á að bera saman fyrstu tvö stökin í hvorum lista fyrir sig og afritar minna stakið (eða stærra ef raða á stærsta stakinu fyrst) í nýjan lista. Heldur síðan áfram og ber þá fyrsta stakið í listanum sem var með hærra stak í fyrsta samanburðinum við annað stakið í seinni listanum.

Röðunaraðferðin býr til þessa tvo röðuðu lista með því að skipta upprunalega listanum sem á að raða í tvennt, síðan hvorum þessarra nýju lista í tvennt aftur og svo framvegis þangað búið er að búta upprunalega listann niður í lista sem einungis geyma eitt stak hver. Að því loknu eru þessir einingalistar sameinaðir tveir og tveir í einu og mynda þá raðaðan lista með tveimur stökum. Því næst eru þeir listar sameinaðir og svo framvegis þangað til allir undirlistar hafa verið sameinaðir í heilan fullraðaðan lista.

Algrím fyrir sameiningarröðun
Hugmyndin bakvið sameiningarröðun byggir á eftirfarandi:
 Hver listi sem inniheldur ekkert eða eitt stak er raðaður.
 Hverjum lista er skipt í tvennt (má muna einu staki ef heildarfjöldi staka er oddstæð tala).
 Sömu aðferð er svo beitt rakið á hvorn helming fyrir sig.
 Að lokum eru listarnir, sem þá eru raðaðir, sameinaðir.

Tvennt liggur að baki hraðvirkni algrímsins: 
 Færri skref þarf til að raða stuttum listum.   
 Færri skref þarf til þess að sameina tvo raðaða lista í raðaðan lista en þarf til þess að sameina tvo óraðaða lista í raðaðan lista.

Eftirfarandi er dæmi um sameiningarröðun á blendingsmáli:

 function mergesort(m)
     var list left, right, result
     if length(m) ≤ 1
         return m
     else
         var middle = length(m) / 2
         for each x in m up to middle
             add x to left
         for each x in m after middle
             add x to right
         left = mergesort(left)
         right = mergesort(right)
         result = merge(left, right)
         return result

Útfæra má sameiningarstefið (e. merge) með ýmsum hætti, hér er einföld útfærsla á blendingsmáli:

 function merge(left,right)
     var list result
     while length(left) > 0 and length(right) > 0
         if first(left) ≤ first(right)
             append first(left) to result
             left = rest(left)
         else
             append first(right) to result
             right = rest(right)
     if length(left) > 0 
         append rest(left) to result
     if length(right) > 0 
         append rest(right) to result
     return result

Heimildir


Flokkur:Röðunarreiknirit

no:Sorteringsalgoritme#Flettesortering