Сортировка фон Неймана
Метод фон Неймана (1945 г.) использует тот факт, что некоторые группы элементов уже упорядочены в исходной последовательности. Используются две области памяти, назовем их A и B. В исходном состоянии таблица находится в области A. Сначала выполняем слияние отрезков упорядоченности, начинающихся на
 |
разных концах таблицы (рис. 36).
Рис 36. Сортировка фон Неймана
Результат слияния помещается в начало области В. Затем от достигнутых позиций продолжаем движение по области А (вторая строка рис. 35), помещая результат, начиная с последней позиции в области B. Следующий процесс слияния вновь помещает результат в левую часть области B, начиная от уже заполненных позиций. Таким образом, двигаемся по области А слева направо и справа налево, помещая результаты слияния поочередно в левую и правую часть области В до тех пор, пока перенос всех данных из области А в область В не будет завершен. В результате такого переноса число отрезков упорядоченности уменьшится вдвое. Затем тот же процесс повторяется для переноса из области В в область А. Алгоритм заканчивает свою работу, когда в результате очередного переноса из области в область, будет получен единственный отрезок. Текст алгоритма приведен ниже.
void Join(int A[], int B[], int *left, int *right,
int *kl, int *kr, int Step){
// Выполняется слияние отрезков массива ключей A:
// левого, начиная с *left и правого, начиная с *right
// ( по ходу дела *left, *right изменяются)
// результат слияния помещается в массив B, начиная с
// *kl или *kr, которые изменяются с шагом Step. Step=1,
// если результат слияния помещается в b слева направо и
// Step=-1, если справа налево
bool l=true,r=true; // признаки того, что участок
// упорядоченности (left,right) еще не кончился
int v;
while(l || r){
// найдем v - меньший ключ в сливаемых отрезках
if(l && (!r || A[*left] <= A[*right])){
v=A[(*left)++];
l=(*left<*right && A[*left] >= A[*left-1]);
} else {
v=A[(*right)--];
r=(*right>*left && A[*right] >= A[*right+1]);
}
if(Step==1){
B[(*kl)++]=v;
} else {
B[(*kr)--]=v;
}
}
}
//------------------------------------------------
int Prohod(int A[], int B[], int N){
// функция выполняет перекачку из области A в область B
// и возвращает число отрезков упорядоченности в области B
int left,right,kl,kr;
int Count,Step;
left=0; right=N-1; kl=0; kr=N-1; step=1;Count=0;
while(left<right){
Join(A,B,&left,&right,&kl,&kr,Step);
if(right==left){
B[kl]=A[left];
Count++;
}
Count++;
Step=-Step;
}
return Count;
}
//----------------------------------------------
void Neumann(int N, int A[]){
int *B;
bool flag=false; // если flag=false, то выполняем
// перекачку из A в B
int *from,*to;
B=new int[N];
do {
if(flag){
from=B;
to=A;
} else {
from=A;
to=B;
}
flag=!flag;
} while(Prohod(from,to,N) > 1);
if(flag){
memcpy(A,B,N*sizeof(int));
}
delete [] B;
}
Время работы сортировки пропорционально 
, так как потребуется не более 
переходов из области в область, и при каждом переходе проходятся все данные.