Сортировка фон Неймана

  Метод фон Неймана (1945г.) использует тот факт, что некоторые группы элементов уже упорядочены в исходной последовательности. Используются две области памяти, назовем их A и B. В исходном состоянии таблица находится в области A. Сначала выполняем слияние отрезков упорядоченности, начинающихся на разных концах таблицы.
    
Результат слияния помещается в начало области В. Затем от достигнутых позиций продолжаем движение по области А (вторая строка рисунка), помещая результат, начиная с последней позиции в области B. Следующий процесс слияния вновь помещает результат в левую часть области B, начиная от уже заполненных позиций. Таким образом, двигаемся по области А слева направо и справа налево, помещая результаты слияния поочередно в левую и правую часть области В до тех пор, пока перенос всех данных из области А в область В не будет завершен. В результате такого переноса число отрезков упорядоченности уменьшится вдвое. Затем тот же процесс повторяется для переноса из области В в область А. Алгоритм заканчивает свою работу, когда в результате очередного переноса из области в область, будет получен единственный отрезок.
  Время работы сортировки пропорционально log2N, так как потребуется не более log2N переходов из области в область, и при каждом переходе проходятся все данные.