который сортирующие алгоритмы дают рядом / приблизительный вид раньше?

Вы можете проверить алгоритм сортировки оболочки.

Насколько я знаю, это единственный алгоритм, который вы можете использовать с субъективным сравнением (что означает, что у вас не будет никаких подсказок о средних значениях). или около того), которая будет приближаться к правильной сортировке на каждом проходе.

Вот дополнительная информация http://en.wikipedia.org/wiki/Shell_sort

как насчет сортировки слева направо и преждевременной остановки бита (каламбур)?

это будет время выполнения Nb, где b - количество битов вы решили изучить. чем больше битов вы изучите, тем более отсортированным будет

несортированный:
5 0101
8 1000
4 0100
13 1101
1 0001

после 1 бит (N):
5 0101
1 0001
4 0100
13 1101
8 1000

после 2 бит (2N)
1 0001
5 0101
4 0100
8 1000
13 1101

и так далее ...

Я бы предложил некоторую версию быстрой сортировки. Если вы знаете, в каком диапазоне находятся данные, которые вы хотите отсортировать, вы можете с умом выбрать сводные элементы и, возможно, разделить проблему более чем на две части одновременно.

Мой полностью ненаучный и визуальный обзор сортов на этой странице показывает, что "Сортировка гребнями" выглядит хорошо. Кажется, с каждым проходом оно приближается к лучшему.

Я думаю, пузырьковая сортировка. Преимущество состоит в том, что вы можете постепенно улучшать порядок с помощью дополнительных разверток данных.