Scalanie posortowanych tablic

Sortowanie przez scalanie polega na podzieleniu sortowanej struktury danych na dwie części, następnie na rekurencyjnym sortowaniu każdej z tych części i ponownym scaleniu już posortowanych części w jedną całość. Warto wiedzieć, że jako pierwszy tę metodę opisał John von Neumann, znany jako twórca m.in. teorii gier oraz koncepcji automatów komórkowych. Algorytm sortowania przez scalanie oparty jest na metodzie dziel i zwyciężaj.

Wyobraźmy sobie, że mamy dwie półki, każda z losową liczbą książek. Książki na półkach ułożone są w kolejności alfabetycznej. Naszym celem jest ułożenie wszystkich książek na trzeciej półce, w kolejności alfabetycznej. By to zrobić, porównujemy ze sobą pierwszą książkę z półki nr 1 z pierwszą książką na półce nr 2. Książka z literą położoną wcześniej w alfabecie, zostaje przeniesiona na trzecią półkę. Czynność powtarzamy, porównując książki, które ułożone są jako pierwsze na półkach. W momencie, gdy skończą nam się książki na jednej z półek, resztę książek z drugiej półki po prostu przenosimy na koniec naszej trzeciej, dodatkowej półki. Aby lepiej zrozumieć algorytm scalania książek na półkach, przeanalizuj rysunek.

R1CBKFZXF9EVP

Ilustracja przedstawia scalanie posortowanych tablic. Ilustracja podzielona jest na pięć części, w każdej znajdują się trzy tablice.
Część pierwsza, w tablicy 1 znajdują się książki z literami A, E, w 2 z B, K, M, trzecia jest pusta.
W części drugiej w tablicy 1: E, w tablicy 2: B, K, M, w tablicy 3: A.
W części trzeciej w tablicy 1: E, w tablicy 2: K, M, W tablicy trzeciej: A, B.
W części czwartej tablica 1 jest pusta, w tablicy 2: K, M, w tablicy 3: A, B, E.
W części piątej tablica 1 oraz 2 są puste, w tablicy trzeciej znajdują się książki z oznaczeniami: A, B, E, K, M.

Etapy sortowania przez scalanie

Chcemy uporządkować niemalejąco n-elementową tablicę liczb całkowitych. W jaki sposób to zrobić, korzystając z metody sortowania przez scalanie?

Aby użyć omówionego wcześniej algorytmu scalania, musimy podzielić tablicę na mniejsze, same w sobie posortowane tablice. W tym celu tablicę dzielimy na pół – jeżeli liczba elementów jest nieparzysta, pierwsza tablica będzie miała jeden element więcej.

Proces powtarzamy do momentu, w którym osiągniemy tablice jednoelementowe.  Wiemy, że tablica posiadająca jeden element już jest posortowana. Dzięki temu możemy scalić dwie tablice jednoelementowe i uzyskać kolejną, posortowaną dwuelementową tablice. Następnie możemy scalić dwie posortowane tablice dwuelementowe, aby uzyskać czteroelementową itd. Przejdźmy do rysunku przedstawiającego kolejne etapy sortowania przez scalanie na podstawie przykładowej tablicy.

R19TR1Q5H8B3S

Ilustracja przedstawia sortowanie przez scalanie liczby: 85924173. W klamrze opisanej jako podziel znajduje się: liczba pierwotna podzielona na dwie różne części: 8592 oraz 4173.
Następnie znów są dzielone na dwie części: 85, 92 oraz 41, 73.
Następnie pojedyńcze liczby sortowane są rosnąco: 58, 29 oraz 14, 37.
Następnie liczby są scalane: 2589 oraz 1347.
Efektem końcowym jest liczba 123456789.

Słownik