Последовательность разбиваетьяс на две половины меньшего размера, сортируеться каждая половина отдельно, после чего они объеденяються в одну. И рекусривное разбиение на меньшие происхожит до тех пор, пока размер этих частей не станер равным единицы.
Procedure Merge(Var A: TArr1; L, M, R:TInd);
Var i, j: TInd;
Key: TEL;
Begin
For j:=M+1 To R Do Begin
Key:=A[j];
{ Добавить A[j] к отсортированной части A[1..j-1] }
i:=j-1;
While (i>0) And (A[i]>Key) Do Begin
A[i+1]:=A[i];
i:=i-1;
End;
A[i+1]:=Key;
End;
End;
Procedure Merge_Sort(Var A: TArr1; L, R:TInd);
Var M: TInd;
Begin
If L<R Then Begin
M:=(L+R) Div 2;
Merge_Sort(A, L, M);
Merge_Sort(A, M+1, R);
Merge(A, L, M, R);
End;
End;
Существуют алгоритмы основанные на обмены двух соседних эллементов, это метод пузыркя и шейкерная сортировка, обе имеют сложность N^2. Однако и по скорости рабоы на любых входных данных и по простоте реализации они проигрывают другим простым сортировкам