Algorytm Forda-Johnsona cz I.

Spróbujmy posortować ciąg 5 liczb za pomocą 7 porównań. Oznaczmy te elementy jako a, b, c, d oraz e. Porównajmy element a z elementem b i załóżmy, że a jest mniejszy (ew. zamieńmy a z b miejscami). Porównajmy element c z d i przyjmijmy, że element c jest mniejszy. I wreszcie porównajmy element a z c i przyjmijmy, że element a jest mniejszy. Wykonaliśmy do tej pory 3 porównania, a sytuację w której się znaleźliśmy przedstawia poniższy rysunek.Spróbujmy teraz wcisnąć element e gdzieś do ciągu [a, c, d]. Możemy to zrobić za pomocą dwóch porównań (użyjemy wyszukiwania binarnego). Najpierw element e sprawdzamy z elementem c. Jeśli jest mniejszy to sprawdzamy z elementem a; w przeciwnym przypadku z elementem d. Trudno przewidzieć w którym miejscu stanie element e. Rozważmy dwa przypadki. Albo e jest najmniejszym elementem z tej trójki (a, c, d), albo nie jest. Ten drugi przypadek przedstawia poniższy rysunek.Jedyną rzeczą jaką trzeba teraz zrobić to wstawić element b pomiędzy elementy {c, d, e}. Identycznie jak poprzednio możemy to zrobić w dwóch ruchach.
W drugim przypadku, gdy element e jest najmniejszy, wystarczy element b porównać tylko z elementami c oraz d. To też możemy zrobić używając dwóch ruchów.

Reasumując. Na początku porównując elementy a, b, c oraz d - wykonaliśmy 3 porównania. Wpychając element e pomiędzy elementy [a, c, e] wykonaliśmy dodatkowe 2 porównania. Na końcu ustawiliśmy element b na swoje miejsce używając nie więcej niż 2 porównań. 3 + 2 + 2 = 7

W następnej notce uogólnimy ten algorytm na tablicę n-elementową.