Сортиране чрез сливане, dev64

Програмиране

Сортирането чрез сливане се състои в последователно разделяне на сортирания масив наполовина, сортиране на половините отделно и след това обединяване на двата сортирани масива в един резултатен масив. Разполовяването се извършва рекурсивно, докато размерът на сортирания масив стане 1 или 2. Ако размерът на масива е 1, тогава връщаме нов масив от един елемент (нищо не трябва да се сортира), ако размерът е 2, тогава сравняваме 2 елемента и връщаме масив от 2 елемента, или в същия ред, или в пренареден ред. В зависимост от това дали елементите в оригиналния масив вървят правилно.

По-долу е изходният код. Функцията merge() обединява два сортирани масива в един (използва се в mergeSoft()). Функцията mergeSort() сортира и обединява рекурсивно.

• testMerge() - показва работата на merge()
• testMergeSoft() - тества mergeSoft()

Асимптотичната сложност на такъв алгоритъм за сортиране е O(n * ln n). Също така е важно да знаете, че по-бавните алгоритми могат да работят по-бързо в определен диапазон от (0 до n>0). Следователно по-бързият алгоритъм не винаги превъзхожда по-бавния. Например, ако сравним сортирането чрез вмъкване със сортирането чрез сливане, тогава се оказва, че сортирането чрез сливане превъзхожда обикновеното сортиране чрез вмъкване само за достатъчно големи n. Първоначалният източник гласи, че сортирането чрез сливане превъзхожда сортирането чрез вмъкване, когато n > 30. Мисля, че този брой може да е по-висок поради необходимостта от разпределяне на допълнителна памет.

---