Sortowanie przez scalanie

Sortowanie przez scalanie

Algorytm sortowania oparty na metodzie dziel i zwyciężaj, dzielący tablicę na mniejsze części, które są następnie scalane w uporządkowaną całość.

Czas działania

Czas działania sortowania przez scalanie wynosi $\displaystyle O(n imes ext{log} n)$ w najlepszym, średnim i najgorszym przypadku.

Stabilność sortowania

Sortowanie przez scalanie jest algorytmem stabilnym, co oznacza, że zachowuje względną pozycję elementów o równych kluczach.

Algorytm dziel i zwyciężaj

Podejście algorytmiczne polegające na dzieleniu problemu na mniejsze podproblemy, które są łatwiejsze do rozwiązania.

Ośrodek dzielenia

W sortowaniu przez scalanie tablica jest dzielona w punkcie środkowym na dwie części.

Scalanie

Proces łączenia dwóch uporządkowanych tablic w jedną uporządkowaną tablicę.

Wymagania pamięciowe

Sortowanie przez scalanie wymaga dodatkowej pamięci $\displaystyle O(n)$ do przechowywania scalanych tablic.

Przykład zastosowania

Sortowanie przez scalanie jest często używane w przypadku dużych zbiorów danych, gdzie stabilność i efektywność są kluczowe.

Różnica między sortowaniem szybkim a scalaniem

Sortowanie szybkie jest bardziej efektywne średnio, ale nie jest stabilne, podczas gdy sortowanie przez scalanie jest stabilne.

Algorytm rekurencyjny

Sortowanie przez scalanie jest algorytmem rekurencyjnym, co oznacza, że wywołuje sam siebie na mniejszych podproblemach.

Krok scalania

W kroku scalania porównuje się elementy z dwóch tablic i przepisuje je do nowej, uporządkowanej tablicy.

Złożoność przestrzenna

Złożoność przestrzenna dla sortowania przez scalanie wynosi $\displaystyle O(n)$, co wynika z dodatkowej pamięci potrzebnej do scalania.

Wydajność w praktyce

Sortowanie przez scalanie jest często bardziej wydajne dla dużych zbiorów danych niż inne algorytmy sortujące, np. sortowanie bąbelkowe.

Zastosowanie w bazach danych

Używane w bazach danych ze względu na stabilność i deterministyczną złożoność czasową.

Podział rekurencyjny

Podział tablicy następuje w sposób rekurencyjny, aż do uzyskania tablic jednoelementowych.