В тази статия се опитвам да използвам всички функции на Golang, така че да направим сортиране чрез сливане по най-оптимизирания начин, който използва многоядрените процесори.

Сортирането чрез сливане е един от най-оптимизираните начини за сортиране с времева сложност O(n log n). Основният принцип е, че е по-евтино да разделите масива на 2 части и да ги сортирате поотделно и да ги обедините накрая.

Нека кодираме най-елементарната форма:

Обърнете внимание, че тук всяка функция за разделяне и сливане се извършва по последователен начин.

Един очевиден начин за оптимизиране тук би бил да направите сортирането на 2-те части едновременно. т.е. ако A с дължина 2x се раздели на X & Y с размер x всеки, сортирането им може да се осъществи едновременно, тъй като едно и също място в паметта не е достъпно от двете процедури за сортиране.

Това прави процеса на разделяне/сортиране по-бърз, тъй като всяко сортиране на подмасиви е едновременно (надяваме се паралелно в множество ядра), но Сливаневсе още блокира завършването на индивидуалното сортиране на подмасиви.

Забележете, че тук разделянето се извършва едновременно, но сливането се извършва последователно.

За да направим целия процес едновременен, какво ще стане, ако не чакаме завършването на сортирането на отделния подмасив за сливане, а вместо това започнем сливането, когато и когато получим нови сортирани елементи във всеки масив.

Как става това по-бързо?

Спомнете си, че обединеният масив взема по един елемент от всеки сортиран подмасив в итерация. Ако цената на всяко сравнение е Cцената за изграждане на обединен масив с размер N от отделни подмасиви ще бъде ~ O(C*N ). Следователно, ако размерът на крайния масив е M, общата цена ще бъде ∑C*(M+2*(M/2)+4*(M/4)+….) = C*M*log(M)е O(M*log(M)), тъй като всяка операция по сливане е блокирана при завършване на сливането на съставните му подмасиви.

Едновременното сливане, от друга страна, не чака завършването на всеки слой от дървото и следователно стойностите се изпомпват, когато и когато бъдат получени.

Имайте предвид, че операцията за разделяне е O(1).

Как да наложим това?

Каналите могат да се използват за изпращане и получаване на данните и следователно, след като първоначалните елементи бъдат получени, операцията по сливане може да започне и няма да бъде блокирана при завършване на по-ранното сливане.

Тази версия на сортиране чрез сливане използва всички функции на Golang за налагане на едновременност. От сортиране до сливане (и без блокиране до завършване). Както можеше да се досетите досега, времевата сложност (приемайки многоядрени, т.е. безкрайни ядра за справяне с натоварването) намалява от O(N*log(N)) на O( log(N)+N), т.е. времето за изграждане на крайния масив е N + височината на дървото (log N)което е O(N ).

Не твърдя, че времевата сложност за сортиране чрез сливане е O(N)!
Твърдение: Оптимизираното сортиране чрез сливане в множество ядра на процесора може значително да намали времето за изпълнение до това, което би изпълнил алгоритъм O(N).

Дано хората открият красотата на Голанг и да допринесат за същото!