Это не так. Имея 4 значения, можно составить математическое выражение, которое даёт одно из 16 возможных значений в зависимости от того, как распределяются эти значения в результате сортировки (ещё проще - получить номер имнимального), после чего использовать предопределённые команды переприсвоения из массива. При этом явно будет использовано ровно 1 сравнение на каждом этапе (более того, можно обойтись вообще без явных сравнений).
Впрочем, это не влияет на сложность алгоритма - он получается гарантированно линейным O(n).

на какой машитне это будет исполняться? если это обычный современный х86, то есть смысл думать о параллельном алгоритме под 64 разрядную архитектуру, думать о кешировании внутри процессора, если же под виртуальную джава или дотнет машину, то нужно смотреть какие там есть команды,
и для правильного ответа надо знать, насколько отличается задержка и скорость чтения из ОЗУ от скорости чтения процессорных регистров, 

а если задача имеет чисто академический интерес, то гораздо гемморнее будет доказывать оптимаьность алгоритма, чем его придумываение. 

я начинаю думать, что нужен какой-то механизм для выделения ответов, чтобы они были более заметны 

уже десяток посто назад был дан ответ:


ну и на вопрос "как он устроен?" - тоже:




Это сообщение отредактировал(а) maxim1000 - 15.12.2010, 09:46

Мне лично больше по вкусу рецепт Peter'a, просто и со вкусом:

Легко перенести на случай Х максимальных, к тому же за один проход массива О(N). Единственное замечание - для предложенной реализации элементы массива должны быть уникальны.