Formalne przedstawienie problemu

Merge sort, czyli sortowanie przez scalanie to algorytm sortowania danych, stosujący metodę dziel i zwyciężaj.

Opis działania algorytmu zamyka się w trzech krokach:

• Podziel dane na dwie równe części,

• Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element,

• Scal posortowane podciągi w jeden.

Sama procedura scalania dwóch ciągów w jeden wygląda następująco:

Dane wejściowe:

d[lewy..sr-1,sr..prawy] - tablica zawierająca dwa ciągi przygotowane do scalenia (jeden ciąg zajmuje indeksy od lewy do sr-1, a drugi ciąg zajmuje indeksy od sr do prawy)

Oczekiwany wynik:

d[lewy..prawy] - docelowa tablica zawierająca posortowany ciąg (scalony)

Dla ułatwienia, wartości scalimy najpierw do tablicy pomocniczej t[lewy..prawy], a po zakończeniu scalania przepiszemy wszystko do tablicy d.

Rozwiązanie:

• Utwórz zmienne wskazujące na początki scalanych ciągów i=lewy, j=sr

• Jeżeli ciąg lewy wyczerpany (i>=sr), dołącz pozostałe elementy ciągu lewego do wynikowego oraz zakończ pracę.

• Jeżeli ciąg prawy wyczerpany (j>prawy), dołącz pozostałe elementy ciągu prawego do wynikowego i zakończ pracę.

• Jeżeli d[i] ≤ d[j] dołącz d[i] do t i zwiększ i o jeden, w przeciwnym przypadku dołącz d[j] do t i zwiększ j o jeden

• Powtarzaj od kroku 2 aż wszystkie wartości z d trafią do t

Teraz można przepisać scalony ciąg z tablicy t do tablicy d.

Implementacja