sortowanie listy (dwukierunkowej) Mariusz: Jeżeli glowa[L] != ogon[L] 1. Wybieramy element rozdzielający Element którego klucz będzie porównywany z kluczami pozostałych elementów Najszybszy dostęp mamy do głowy i ogona innych węzłów trzeba szukać a więc mamy do nich liniowy czas dostępu 2. Z węzłów oryginalnej listy tworzymy trzy podlisty zależnie od wyniku porównania wartości kluczowych oryginalnej listy z wartością kluczową elementu rozdzielającego Do tego etapu możemy wykorzystać operacje na kolejce Najpierw zdejmujemy element z oryginalnej listy , porównujemy wartość kluczową zdjętego elementu z wartością elementu rozdzielającego i wstawiamy element do jednej z trzech podlist z których pierwsza zawiera tylko węzły o kluczach mniejszych niż klucz węzła rozdzielającego druga zawiera tylko węzły o kluczach równych kluczowi węzła rozdzielającego trzecia zawiera tylko węzły o kluczach większych niż klucz węzła rozdzielającego Podlisty są tworzone z istniejących węzłów i nie ma potrzeby alokować pamięć na nowe węzły 3. Rekurencyjne wywołanie procedury sortującej na podlistach zawierających węzły o kluczach różnych niż klucz węzła rozdzielającego 4. Łączenie posortowanych podlist w jedną posortowaną listę Tutaj łączenie redukuje się do tzw konkatenacji Jak na podstawie tego opisu algorytmu napisać procedurę sortującą np z przedstawieniem krokowego działania algorytmu W tym podejściu gdy uda nam się napisać operacje na kolejce i konkatenację list to dalej powinno być łatwo