Merge sort

24 Nov

Merge sort je primitivní řadící algoritmus fungují na následujícím principu:

  1. Rozdělit seznam čísel na dvě poloviny
  2. Opakovat krok 1 dokud nemám více jak dva elementy
  3. Seřadit je a poté oba podlisty smíchat

V praxi to znamená, že rekurzivně smíchávám dvojce seznamů, dokud nemám seřazeno.
Následující pomalá gif animace to výborně a polopaticky vysvětluje:

Merge sort má efektivnost O(n log n). Merge sort je, díky svému principu, velmi efektivní například na smíchání dvou seznamů čísel, které už seřazené jsou, nebo i přidávání neseřazeného seznamu k seřazenému. Může také výborně fungovat paraelně, jednotlivé poloviny se dají řadit nezávisle na sobě.

Implementace Merge sortu v pseudokódu:

function merge_sort(seznam):
  if len(seznam)<=1 return seznam
  leva = merge_sort(seznam[:len(seznam)//2])
  prava = merge_sort(seznam[len(seznam)//2:])
  vysledek = smichat(leva, prava)
  return vysledek

Funkce smichat může mít více implementací.


Zdroj obrázku: http://bamsoftware.com/hacks/sorts/ (podívejte se tam)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: