Wykład ten składa się z dwóch części. W pierwszej zajmiemy się badaniem złożoności problemu sortowania przez porównywanie elementów. Udowodnimy, że każdy algorytm sortujący ciąg n elementowy musi w najgorszym razie wykonać co najmniej O(n´lgn) porównań. Zbadamy też dolne oszacowanie złożoności algorytmów sortowania przez porównywanie elementów w przypadku średnim.  Wywnioskujemy stąd, że algorytm QuickSort jest algorytmem optymalnym ze względu na średnią złożoność czasową.

W drugiej części wykładu omówimy algorytmy sortowania, które wykorzystują pewne specjalne cechy sortowanych elementów i albo nie wykonują wcale porównywania elementów, albo wykonują je w niewielkim stopniu. Wspólna idea tych algorytmów polega na rozrzucaniu elementów, ze względu na pewien klucz, do "koszyków" lub "kubełków", realizowanych jako listy, kolejki, czy tablice. Omówimy trzy najbardziej znane algorytmy: algorytm sortowania przez zliczanie (CountingSort), algorytm sortowania pozycyjnego (RadixSort) i algorytm kubełkowy (BucketSort). Wszystkie te algorytmy mają złożoność liniową ze względu na rozmiar danych. Podkreślmy jeszcze raz, że nie ma tu sprzeczności z wynikami uzyskanymi dla algorytmów sortowania działających w modelu drzew decyzyjnych. Algorytmy CountingSort, RadixSort, BucketSort nie należą do tej klasy algorytmów.