dlaczego sortowanie scalające jest preferowane niż szybkie sortowanie do sortowania połączonych list

Szybkie sortowanie działa dobrze do sortowania w miejscu. W szczególności większość operacji może być zdefiniowana w kategoriach zamiany par elementów w tablicy. Aby to zrobić, zwykle "przechodzisz" przez tablicę za pomocą dwóch wskaźników (lub indeksów itp.) Jeden zaczyna się na początku tablicy, a drugi na końcu. Oba następnie działają w kierunku środka (i skończysz z konkretnym krokiem partycji, gdy się spotkają). To jest drogie z plikami, Ponieważ pliki są zorientowane przede wszystkim w kierunku czytania w jednym kierunku, od początku do końca. Zaczynanie od końca i szukanie do tyłu jest zwykle stosunkowo drogie.

Przynajmniej w najprostszym wcieleniu, sortowanie scalające jest prawie odwrotnie. Łatwy sposób implementacji wymaga tylko przeglądania danych w jednym kierunku, , ale polega na rozbiciu danych na dwa oddzielne kawałki, sortowaniu kawałków, a następnie łączeniu ich z powrotem.

Z linkowaną listą łatwo jest wziąć (na przykład) elementy naprzemienne w jednej połączonej liście i manipulować łączami, aby utworzyć dwie połączone listy z tych samych elementów zamiast. W przypadku tablicy, przestawianie elementów tak, aby przemienne elementy trafiały do oddzielnych tablic jest łatwe, jeśli chcesz utworzyć kopię tak dużą jak oryginalne dane, ale poza tym bardziej nietrywialną.

Podobnie Scalanie z tablicami jest łatwe, jeśli scalasz elementy z tablic źródłowych w nową tablicę z danymi w kolejności -- ale aby zrobić to w miejscu bez tworzenia zupełnie nowa kopia danych to zupełnie inna historia. W przypadku listy połączonej łączenie elementów z dwóch list źródłowych w jedną listę docelową jest banalne - ponownie, po prostu manipulujesz linkami, bez kopiowania elementów.

Jeśli chodzi o używanie Quicksort do tworzenia posortowanych przebiegów dla zewnętrznego sortowania scalonego, to działa, ale jest (zdecydowanie) nieoptymalne z reguły. Aby zoptymalizować sortowanie scalające, Zwykle chcesz zmaksymalizować długość każdego sortowanego "biegu" podczas jego produkcji. Jeśli po prostu czytasz w danych, które zmieszczą się w pamięci, Quicksort i zapisz, każde uruchomienie będzie ograniczone do (trochę mniej) wielkości dostępnej pamięci.

Z reguły możesz zrobić trochę więcej niż to. Zaczynasz od czytania w bloku danych, ale zamiast używać Quicksort na nim, budujesz stertę. Następnie, gdy zapisujesz każdy element ze sterty do posortowanego pliku "run", wczytujesz kolejny element z Twojego pliku wejściowego. Jeśli jest większy niż element, który właśnie napisałeś na dysku, wkładasz go do istniejącej sterty i powtarzasz.

Elementy, które są mniejsze (tzn. należą do elementów, które zostały już napisane), zachowujesz osobno i budujesz drugą stertę. Gdy (i tylko wtedy, gdy) pierwsza sterta jest pusta, a druga sterta przejęła całą pamięć, kończysz zapisywanie elementów do istniejącego pliku" Uruchom " i zaczynasz od nowego.

To, jak będzie to skuteczne, zależy od początkowej kolejności danych. W najgorszym przypadku (wejście posortowane w odwrotnej kolejności) nie robi nic dobrego. W najlepszym przypadku (Dane wejściowe już posortowane) pozwala na "sortowanie" danych w jednym przebiegu przez Dane wejściowe. W przeciętnym przypadku (Dane wejściowe w kolejności losowej) pozwala to na około dwukrotne zwiększenie długości każdego posortowanego biegu, co zazwyczaj poprawia prędkość o około 20-25% (choć procent ten różni się w zależności od tego, o ile większe są dane niż dostępna pamięć).