Knuth zostawił to jako ćwiczenie (tom 3, 5.2.5). Istnieją lokalne rodzaje scalania. Muszą być wdrażane ostrożnie.
Po pierwsze, naiwne scalanie w miejscu, takie jak opisane tutaj, nie jest właściwym rozwiązaniem. Obniża wydajność do O (N 2 ) .
Chodzi o to, aby posortować część tablicy, a resztę wykorzystać jako obszar roboczy do scalenia.
Na przykład jak następująca funkcja scalania.
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
Potrzeba tablicę xs, obie tablice podrzędne sortowane są reprezentowane zakresie [i, m)i [j, n)odpowiednio. Obszar pracy zaczyna się od w. Porównaj ze standardowym algorytmem scalania podanym w większości podręczników, ten wymienia zawartość między posortowaną pod-tablicą a obszarem roboczym. W rezultacie poprzedni obszar roboczy zawiera scalone posortowane elementy, podczas gdy poprzednie elementy przechowywane w obszarze roboczym są przenoszone do dwóch pod-macierzy.
Istnieją jednak dwa ograniczenia, które należy spełnić:
- Obszar roboczy powinien mieścić się w granicach tablicy. Innymi słowy, powinien być wystarczająco duży, aby pomieścić elementy wymieniane bez powodowania żadnego błędu spoza zakresu.
- Obszar roboczy może się pokrywać z jednym z dwóch uporządkowanych zestawów; musi jednak zapewnić, że żaden z nie połączonych elementów nie zostanie nadpisany.
Po zdefiniowaniu tego algorytmu scalania łatwo jest wyobrazić sobie rozwiązanie, które może posortować połowę tablicy; Kolejne pytanie brzmi: jak postępować z resztą nieposortowanej części przechowywanej w obszarze roboczym, jak pokazano poniżej:
... unsorted 1/2 array ... | ... sorted 1/2 array ...
Intuicyjnym pomysłem jest sortowanie rekurencyjne innej połowy obszaru roboczego, dlatego jest tylko 1/4 elementów, które nie zostały jeszcze posortowane.
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
Kluczowym punktem na tym etapie jest to, że musimy scalić posortowane 1/4 elementów B z posortowanymi 1/2 elementami A prędzej czy później.
Czy pozostało miejsce do pracy, które mieści tylko 1/4 elementów, wystarczająco duże, aby połączyć A i B? Niestety tak nie jest.
Jednak drugie ograniczenie wspomniane powyżej daje nam wskazówkę, że możemy go wykorzystać, ustawiając obszar roboczy tak, aby zachodził na którąkolwiek z pod-macierzy, jeśli możemy zapewnić łączącą się sekwencję, że nie scalone elementy nie zostaną nadpisane.
W rzeczywistości zamiast sortować drugą połowę obszaru roboczego, możemy posortować pierwszą połowę i umieścić obszar roboczy między dwoma sortowanymi tablicami w następujący sposób:
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
Ta konfiguracja skutecznie rozmieszcza obszar roboczy pokrywający się z podobszarem A. Pomysł ten zaproponowano w [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Praktyczne połączenie w miejscu ''. Nordic Journal of Computing, 1996].
Pozostaje więc tylko powtórzyć powyższy krok, co zmniejsza obszar roboczy z 1/2, 1/4, 1/8,… Gdy obszar roboczy staje się wystarczająco mały (na przykład pozostały tylko dwa elementy), możemy przełącz się na trywialny sposób wstawiania, aby zakończyć ten algorytm.
Oto implementacja w ANSI C na podstawie tego dokumentu.
void imsort(Key* xs, int l, int u);
void swap(Key* xs, int i, int j) {
Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}
/*
* sort xs[l, u), and put result to working area w.
* constraint, len(w) == u - l
*/
void wsort(Key* xs, int l, int u, int w) {
int m;
if (u - l > 1) {
m = l + (u - l) / 2;
imsort(xs, l, m);
imsort(xs, m, u);
wmerge(xs, l, m, m, u, w);
}
else
while (l < u)
swap(xs, l++, w++);
}
void imsort(Key* xs, int l, int u) {
int m, n, w;
if (u - l > 1) {
m = l + (u - l) / 2;
w = l + u - m;
wsort(xs, l, m, w); /* the last half contains sorted elements */
while (w - l > 2) {
n = w;
w = l + (n - l + 1) / 2;
wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */
wmerge(xs, l, l + n - w, n, u, w);
}
for (n = w; n > l; --n) /*switch to insertion sort*/
for (m = n; m < u && xs[m] < xs[m-1]; ++m)
swap(xs, m, m - 1);
}
}
Gdzie wcześniej zdefiniowano wmerge.
Pełny kod źródłowy można znaleźć tutaj, a szczegółowe wyjaśnienie można znaleźć tutaj
Nawiasem mówiąc, ta wersja nie jest najszybszym sortowaniem scalającym, ponieważ wymaga więcej operacji wymiany. Według mojego testu jest on szybszy niż standardowa wersja, która przydziela dodatkowe miejsca w każdej rekurencji. Jest jednak wolniejszy niż wersja zoptymalizowana, która z góry podwaja pierwotną tablicę i wykorzystuje ją do dalszego łączenia.