03.com.ua- свободная медицинская энциклопедия. Каждый зарегистрированый участник может редактировать статьи
Сортировка слиянием
Сортировка слиянием (Шаблон:Lang-en) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Пример реализации алгоритма на псевдокоде:
function mergesort(m) var list left, right, result if length(m) ≤ 1 return m else 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 end if
Есть несколько вариантов функции merge(), наиболее простой вариант может выглядеть как
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) end if if length(left) > 0 append left to result if length(right) > 0 append right to result return result
Литература
cs:Merge sort de:Mergesort en:Merge sort eo:Kunfanda ordigo es:Ordenamiento por mezcla fi:Lomituslajittelu fr:Tri fusion he:מיון מיזוג id:Merge sort it:Merge sort ja:マージソート lb:Mergesort lt:Sąlajos rikiavimo algoritmas nl:Mergesort no:Flettesortering pl:Sortowanie przez scalanie pt:Merge sort sk:Triedenie zlučovaním uk:Сортування злиттям vi:Sắp xếp trộn zh:归并排序