Sortowanie przez scalanie Mariusz: Cormen w swym pseudokodzie używa wartowników i używa dwóch pomocniczych tablic zamiast jednej Według mnie wartownicy są niepotrzebni U niego procedura sortująca jest rekurencyjna chociaż można ją zapisać iteracyjnie (Wikipedia twierdzi że trzeba zacząć od łączena podtablic długości 1 w podtablice długości 2 itd)

jc: Oto kod bez wartowników. Działa, ale coś nalezałoby poprawić. Sklejając przepisuję do tablicy pomocniczej t[ ] pierwszy fragment, jednak przy sklejaniu iteracynym "sortuj2" pierwszy fragment może być prawie tak długi, jak cała tablica. Na pewno można to poprawić odwracając kierunek ruchu w funkcji sortuj2 lub w funkcji sklej. void sklej(int *p, int *s, int *k, int *t){ int *q, *r; for( q = p, r = t; q < s; q++, r++) *r = *q; while(t < r && s < k) if(*t < *s) *(p++) = *(t++); else *(p++) = *(s++); while(t < r) *(p++) = *(t++); } void sortuj(int * p, int * k, int* t){ if( k − p <= 1) return; int * s = p + (k−p)/2 ; sortuj(p,s,t); sortuj(s,k,t); sklej(p,s,k,t); } void sortuj2(int *p, int *k, int*t){ int *r; int m; for(m = 1; m < k−p; m *=2){ for(r = p; r < k−m; r += 2*m) if(r+2*m < k) sklej(r, r+m, r+2*m, t); else sklej(r, r+m, k, t); }

Mariusz: Czyli złożoność jest zbliżona do quick sorta (oczywiście asymptotycznie) ? Na wikipedii twierdzą że można zapisać procedurę sortującą iteracyjnie bez straty złożoności czasowej Twierdzą także że stracilibyśmy na złożoności czasowej gdybyśmy chcieli zaimplementować sortowanie przez scalanie w miejscu

Mariusz: Parę razy zapisałem sobie na kartce przebieg procedur sortujących przez scalanie i mam jednak mam wątpliwości czy to że czasami podtablice nie będą miały mniej więcej tyle samo elementów popsuje złożoność czasową

jc: Usuń przypadkową klamerkę wewnątrz sortuj2(). Wykonałem doswiadczenie. Wydaje się, że wersja iteracyjna działa o 10% szybciej. Teoretycznie pewnie tak samo szybko. Przy okazji. Mam sortowanie przez scalanie wmiejscu, teoretycznie wolniejsze: n (ln n)², chodź mogę już dobrze nie pamiętać.

Mariusz: Działa ci ten kod bo jak go skopiowałem to nie przestawia elementów

Mariusz: W przypadku sortowania listy wystarczy przestawiać wskaźniki na następny bądź poprzedni element