Niech \( (U,\le) \) będzie zbiorem liniowo uporządkowanym z relacją porządkującą \( \le \) i niech \( c_1, c_2, \ldots, c_n \) będzie ciągiem \( n \) elementów z \( U \), dla pewnego całkowitego \( n > 0 \). Należy znaleźć permutację \( c_{i_1}, c_{i_2},\ldots,c_{i_n} \) taką, że \( c_{i_1}\le c_{i_2}\le \ldots \le c_{i_n} \).
Uwaga: dla pary elementów \( x, y \in U \) będziemy pisali \( x < y \) (\( x > y \)), gdy \( x \le y \) (\( y \le x \)) oraz \( x \ne y \).
W tym wykładzie przyjmujemy, że elementy ciągu \( c \) znajdują się w tablicy \( a[1..n] \), tzn. \( a[1] = c_1, a[2] = c_2, \ldots, a[n] = c_n \). Będziemy także chcieli, żeby posortowany ciąg \( c \) znajdował się nadal w tablicy \( a \), tzn. wynikiem sortowania ma być \( a[1] = c_{i_1} \le a[2] = c_{i_2} \le \ldots \le a[n] = c_{i_n} \). Dla wygody dalszych rozważań przyjmijmy, że tablica \( a \) jest indeksowana od \( 0 \), i że \( a[0] \) zawiera element, który nie jest większy od żadnego elementu z \( a[1..n] \), tzn. dla każdego \( i = 1,2, \ldots, n \), \( a[0] \le a[i] \).
Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z \( U \). Na \( U \) mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i \( U \) może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy \( a \) jest porównywanie jej elementów parami. Operacja porównania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy \( a \), potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Operacją tą będzie operacja \( Exchange(i,j) \) polegająca na zamianie elementów w tablicy \( a \) z pozycji \( i \) oraz \( j \), \( 1\le i, j \le n \).