студентикВ принципе, у меня была идея подобной сортировки может быть только несколько отличная.
1. Разбить все элементы на группы(возможно рекурсивно) числом элементов мин - 1 макс - 2.
2. Упорядочить элементы в каждой группе для этого достаточно 1 сравнения для 1 групы
3.Упорядоченные группы сливать например слева направо.

Если не ошибаюсь порядок действий такой сортировки равен исходному числу элементов.
Минус в раходах на доп. память.
Если не ошибаюсь, то ваш алгоритм похож на алгоритм Джона фон Нейманом , изобретенного в 1945 году. Вот его корректная формулировка:

1. Сортируемое поле разбивается на две половины примерно одинакового размера;
2. Каждая из получившихся половин сортируется отдельно, например – этим же алгоритмом;
3. Два упорядоченных буфера половинного размера объединяются (сливаются) в один.

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

«Естественное слияние» отличается от «обычного» учетом уже существующего порядка в сортируемых записях . А поскольку порядок может быть как возрастающий (неубывающий) так и убывающий, то приходится принимать во внимание оба этих случая. Именно этот вариант я и реализовал, для случая одного прохода , определяющего упорядоченные подпоследовательности (УПП) и без рекурсии .

макс132если вы действительно такой хороший, вы должны были дать ссылку на гуглю с описанием, а не объяснять)
Так с ссылками не проблема, например:
http://books.google.ru/books?id=k0vUmjua41wC&pg=PA341&lpg=PA341&dq=%22natural+merge+sort%22
http://books.google.ru/books?id=zInY9G915-YC&pg=PA257&lpg=PA257&dq=%22natural+merge+sort%22
http://books.google.ru/books?id=HZ9Z-PS1g0UC&pg=PA51&lpg=PA51&dq=%22natural+merge+sort%22
http://www.daniweb.com/forums/thread190739.html
Только, они не дают реальный оптимизированный алгоритм, только общие идеи или неудачную реализацию в последнем случае. У меня самого есть три или четыре собственных реализаций этого алгоритма, остановился на том, который продемонстрирован рисунком. И он существенно завязан на двоичном представлении числа упорядоченных подпоследовательностей (УПП) данной последовательности. Так что я никого не копирую, за исключением общих идей.

MasterZivRT183.1 пишет:
> Я при всем моем уважении к Кнуту в руках не держал его книжки.
> Во-первых, они очень дорогие,
> во-вторых, там довольно сложная математика

Не, там далеко не везде сложная математика. Но написано исключительно
занудно и, как бы сказать, замедленно. Кнут вообще людит процесс
написания, видимо, читеть его поэтому сложно.
Зря, вы на Кнута наезжаете. Не нужно забывать, что его третий том «Сортировка и поиск» вышел на русском языке аж в 1978 году, а в оригинале в 1973 году. А основные результаты, очевидно, получены в 60-х годах. Так что для своего времени, когда шла борьба за каждый байт памяти его труды были вполне актуальны. Сейчас, да, есть более современные книги, например.

Роберт Седжвик – Фундаментальные алгоритмы на C++ – Части 1-4 – Анализ & Структуры данных & Сортировка & Поиск
и
Роберт Седжвик – Фундаментальные алгоритмы на C++ – Часть 5 – Алгоритмы на графах

Их можно скачать, например в
http://mskd.ru/?id.17174.books.Fyndamental'nie_algoritmi_na_S++_-_R.Sedzhvik

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

студентикСтранно а я полагал, что все фундаментальные алгоритмы сложились как раз уже во время написания книг Кнутом. Современные алгоритмы, по-моему, не претерпели каких-либо серьезных изменений, кроме как аппаратных уклонов на распараллеливание вычислений, многопроцессорность и т. д.
Ну, того же «natural merge sort» я у Кнута не нашел, хотя про сортировку слиянием он пишет. Потом B+ деревья , которые весьма интенсивно используются при индексации баз данных и построении на их основе SQL запросов изобретены Рудольфом Байером (Rudolf Bayer) только в 1972 году. И вообще, фундаментальные алгоритмы, имеющие отношение к SQL, у Кнута практически отсутствуют полностью. Так что не надо думать, что фундаментальные алгоритмы перестали появляться после Кнута :) .

механизаторEmery
Ну, почему? В военной области, в разработке современных систем вооружений, хорошая «мат. подготовка» очень даже нужна и востребована Ну, и сколько получает средний разработчик форм на vcl/wpf/winforms и сколько получает специалист с хорошей "матподготовкой" в оборонке? Второй в 2-3 раза меньше первого
Трудно судить о зарплате закрытых контор. На западе «военные» программисты получают чуть ли не на порядок больше «обычных». И потом сейчас не лучшая эпоха в наших странах для подобных сравнений. В Украине даже военный парад бронетехники отменили на день независимости из-за банальной нехватки денег. Да и к тому же «рабочие лошадки» у нас всегда получают значительно меньше тех, кто ими «руководит». Короче если политика оплаты труда никак не связана с качеством этого труда, то о чем тут говорить вообще. Раньше был принцип оплаты: «От каждого по способностям, каждому по труду» , а сейчас работает принцип: «От каждого по способностям, каждому сколько положено» :) .

MasterZivДа он не морально устарел, он по жизни такой. Математик, зануда может
быть, максималист. Кто ещё мог отказаться от публикации своей книги только
потому, что не было шрифтов для её издания, уйти на 2 или 3 года, и вернуться
с новым средством производства этих самых шрифтов ?

Это не хорошо и не плохо, это -- свойство характера. Человек пишет
статью о форматировании параграфа и в лирическом отступлении исследует
вопрос о том, как полиграфисты решали, где закончить очередную строку
абзаца, чуть ли не вплоть до рукописных тексов библии или даже
египедских иероглифов. Ну что поделать, такой он.
Как по мне, то эта информация не имеет никакого отношения к профессионализму Кнута. Все равно, что судить про общую теорию относительности Эйнштейна по тому, как он показал язык всему человечеству или как сплагиатил у Лоренца и др. Я могу повторить еще раз, что его книга была весьма актуальна в свое время, и сейчас она имеет больше академический или исторический интерес.

студентикПросмотрел книгу "Фундаментальные алгоритмы на С++" Сэджвика. Неспорю книга хороша, наверно даже более доступна для начинающих, чем Кнут. Но даже беглого взгляда хватило, чтобы увидеть их разницу. Кнут более фундаментален, исчерпывающ, математически строг, именно поэтому наверно его 3х томник считают чуть ли не библией алгоритмов всех времен. Да у Сэджвика более новый материал, более последние факты, но это явно книги разных уровней. Могу даже предположить, что Сэджвик на страницах своей книги в заданиях вряд ли давал научные неразрешенные проблемы, как это делает Кнут. Правда в чем сила Кнута в том наверно его и недостаток, читать его неимоверно трудно - нужно превосходное знание математики и куча свободного времени, поэтому скорее всего он и не используется практиками. По мне его 3 тома нужно лет 5 основательно изучать либо в учебном заведении, либо самостоятельно и тогда откроется истина:) А так конечно Сэджвик даже предпочтительнее...
Ну, вы рассуждаете, действительно как студент :) , т.е. как человек недавно приступивший грызть «гранит науки». На самом деле Кнут «фундаментален» и «исчерпывающ» только для своего времени, не нужно забывать про это. «Математическая строгость» у него относительная, т.к. свои вычисления он проводит для придуманной им виртуальной машины MIX, с ее псевдо ассемблером, которая весьма далека от современных компьютеров и ассемблерного кода. Поэтому я и говорю, что реальную эффективность алгоритмов следует перерассчитывать заново, с учетом собственной специфики. Конечно, у него можно почерпнуть идеологию математических вычислений и несложный математический аппарат уровня первого – второго курса мехмата, но считать это «серьезной математикой» – увольте! Хотя если вас интересует только порядок эффективности алгоритмов (уровня О-символики), без конкретных коэффициентов, то, пожалуйста, спокойно используйте формулы Кнута. Только его «фишка» состояла в том, что он часто точно вычислял неопределенные коэффициенты для алгоритмов своей виртуальной машины. Так что для «Библии» он уже немного устарел.

Ну, что из того, что Кнут в качестве упражнения предложил доказать теорему Ферма, а Сэджвик – нет? Для поиска научных проблем вполне можно использовать другую литературу. Однако, если вы занимаетесь реальной научной работой, то вам собственных «научных проблем» хватит за глаза. У меня даже в курсовых и дипломном проекте, были сформулированы классы задач, которые еще «не знала математика» . Ну и что из того? И практически в каждой статье, посвященной прикладной науке, которыми я «баловался» в свое время я всегда выходил на неизвестные классы математических задач. Причем, все мои исследования были посвящены практическим приложениям. В то время я часто думал, что неплохо было бы привлекать профессиональных математиков для решения этих новых классов задач, и им было бы интересно и прикладной науке полезно. А то они (математики – теоретики) в своей аспирантуре, как правило, решают задачи, которые наверняка еще сотни лет не будут востребованы наукой. К сожалению, для этого у меня не было и нет соответствующих ресурсов. Скажем, недавно мне приходилось консультировать одного к.т.н-а, которому были выделены жалкие финансовые крохи на исследования в области борьбы с газовыделением в шахтах, так вот я с огромным удивлением обнаружил, что гибель шахтеров от взрывов метана и угольной пыли связанна не с «абсолютно случайной, неуправляемой природной стихией», типа землетрясений и вулканов, а с тем, что до сих пор нет адекватной математической модели образования катастрофически быстро растущей трещинноватости в горных породах (часто со сверхзвуковой скоростью) на средних и больших глубинах (для малых глубин матаппарат вполне адекватен). Самое смешное, что есть человек, который занимается проблемой сверхзвукового образования трещин на больших глубинах шахт уже более 20-ти лет. Фамилия его А.В. Шестопалов (ИПКОН РАН, Москва). Но, как легко предположить, и так на самом деле, он как Дон Кихот пытается побороть академическую науку с ее непотопляемыми заблуждениями относительно взрывоопасности в шахтах. А шахтеры, как гибли, так и гибнут. По сути это опальный или оппозиционный ученый. Да, у него сейчас есть собственный сайт и даже сторонники, но нет финансов и поддержки. Когда я ознакомился с его концепцией происхождения взрывов в шахтах, то стразу ему «поверил», в отличие от других ученных, исповедующих традиционные взгляды в этих вопросах. Проблема только за малым, воплотить концепцию Шестопалова в математическую модель. Но у него не хватает математического образования, а добровольные помощники предлагают строить модель на базе конечных автоматов, что вряд ли приведет к успеху, по моему мнению. В данном случае научная проблема сформулирована не мной, но важно другое, что нет пока математиков профессионалов, которые бы «занялись» ею. Прошу прощения, за столь длинный экскурс примера формулирования реальных научных проблем, взамен абстрактно-теоретических (и часто никому не нужных).

Далее по Кнуту. Можно спокойно игнорировать его математику, достаточно конечных формул определяющих порядок производительности алгоритмов (но конкретным коэффициентам особо не следует верить для современных реализаций этих алгоритмов). Потом, знание всех алгоритмов совершенно не обязательно, достаточно общий идей для какого класса задач, какие алгоритмы наиболее подходящи. И 5 лет его совершен не нужно изучать, достаточно пары месяцев и то урывками. Для современного программирования он мало приспособлен. Скажем мне понадобился хороший алгоритм внешней сортировки, так нашел я его не у Кнута, понадобились B+ деревья, их также не было у Кнута. И даже алгоритм быстрой сортировки, который есть у Кнута, гораздо лучше исследован в http://www.codenet.ru/progr/alg/qsort.php . Еще можно рекомендовать «Методы сортировки и поиска» С.Д. Кузнецова http://www.citforum.ru/programming/theory/sorting/sorting2.shtml