Еще в раннем детстве в нас просыпается стремление к разрушению и хаосу — один их базовых инстинктов человека. Но по мере взросления в нем крепнет противоположное начало — тяга к упорядочиванию и систематизации. Появление компьютеров дало возможность работать с куда большими объемами информации. Проблема упорядочивания стала более остро, на нее были кинуты силы лучших умов. В прикладной математике она получила название «задача сортировки».
Надо отдать должное исследователям, постарались они хорошо. Об этом свидетельствует то огромное количество методов, которыми нам предлагают сортировать данные. Зачем же так много? И правда — может, достаточно одного эффективного способа, и не надо морочить себе голову таким обилием? Ответ на этот вопрос состоит в том, что очень трудно иногда бывает сопоставить эффективность двух разных методов. Проще говоря: одни более удобны в одних случаях, другие — в других. Проблемам сортировок Дональд Кнут посвятил целый том своего «Искусства программирования». Попробуем и мы разобраться в этом подробней.
Итак, постановка задачи такова: есть набор неупорядоченных данных (массив), задача — выдать те же данные, упорядоченные по некоторому полю (ключу) по возрастанию (убыванию). Обычно данные представляются в виде ключа и некоторой связанной с ним информации. Например, год рождения и фамилия. Рассмотрим несколько алгоритмов, решающих данную задачу.
Алгоритм 1. Сортировка вставками.
Это изящный и простой для понимания метод. Вот в чем его суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку (Рис. 1). Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после — большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм 
можно реализовать на языке программирования Pascal:
Program InsertionSort; Var A,B : array[1..1000] of integer; N,i,j : integer; Begin {Определение размера массива A (N) и его заполнение} … {сортировка данных} for i:=1 to N do begin j:=i; while (j>1) and (B[j-1]>A[i]) do begin B[j]:=B[j-1]; j:=j-1; end; B[j]:=A[i]; end; {Вывод массива B} … End.
В принципе, данную сортировку можно реализовать и без дополнительного массива B, если сортировать массив A сразу при считывании, т. е. осуществлять вставку нового элемента в массив A.
Алгоритм 2. Пузырьковая сортировка.
Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма (Рис. 2). Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где 
N — количество элементов. Вот как это можно реализовать:
Program BubbleSort; Var A : array[1..1000] of integer; N,i,j,p : integer; Begin {Определение размера массива A (N) и его заполнение} … {сортировка данных} for i:=1 to n do for j:=1 to n-i do if A[j]>A[j+1] then begin {Обмен элементов} p:=A[j]; A[j]:=A[j+1]; A[j+1]:=P; end; {Вывод отсортированного массива A} … End.
Алгоритм 3. Сортировка Шейкером.
Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N — количество элементов. Реализация данного алгоритма выглядит так:
`Program ShakerSort; Var A : array[1..1000] of integer; N,i,j,p : integer; Min, Max : integer; Begin {Определение размера массива A — N) и его заполнение} … {сортировка данных} for i:=1 to n div 2 do begin if A[i]>A[i+1] then begin Min:=i+1; Max:=i; end else begin Min:=i; Max:=i+1; end; for j:=i+2 to n-i+1 do if A[j]>A[Max] then Max:=j else if A[j]q) or (a[i]