4. Часть 4

Created Saturday 11 October 2014

http://habrahabr.ru/post/196226/

Оптимальная сортировка

Сортировка слиянием

def merge(A, B):
if empty(A):
return B
if empty(B):
return A
if A[0] < B[0]:
return concat(A[0], merge(A[1...A_n], B))
else:
return concat(B[0], merge(A, B[1...B_n]))
def mergeSort(A, n):
if n = 1:
return A # already sorted
middle = floor(n / 2)
leftHalf = A[1...middle]
rightHalf = A[(middle + 1)...n]
return merge(mergeSort(leftHalf, middle), mergeSort(rightHalf, n - middle))

Сортировка кучей в ядре Линукс

http://lxr.free-electrons.com/source/lib/sort.c



Backlinks: