مرتب‌سازی روان
مرتب‌سازی روان یک روش مرتب‌سازی بر پایهٔ مقایسه است. این مرتب‌سازی حالتی از مرتب‌سازی درهم است که توسط ادسخر دیکسترا در سال ۱۹۸۱ توسعه یافته‌است. مثل مرتب‌سازی درهم کران بالای مرتب‌سازی روان formula_1 است. مزیت مرتب‌سازی روان این است که وقتی تعدادی از ورودی‌ها مرتب شده باشد پیچیدگی از formula_2 شود در حالی که متوسط پیچیدگی مرتب‌سازی روان formula_1است بدون توجه به مرتب بودن یا نبودن ورودی‌ها
برای اینکه یک آرایه را مرتب کنیم ابتدا آن را به رشته‌ای از پشته‌ها تقسیم می‌کنیم که هر پشته اندازه ی مساوی یکی از اعداد فیبوناچی دارد. فرایند تقسیم ساده‌است -چپ‌ترین گرهٔ آرایه بزرگترین پشته ممکن را ایجاد می‌کند و بقیهٔ عناصر باقی‌مانده هم به همین شکل تقسیم شوند.
هر پشته این خاصیت پشته را که گرهٔ ریشه همیشه بزرگتر مساوی گره‌های فرزند آن ریشه‌است را نگه می‌دارد و ریشهٔ پشته‌ها تمام این خاصیت را که گرهٔ ریشه در هر پشته بزرگتر مساوی گرهٔ ریشهٔ پشته چپ آن است را نگه دارد. نتیجه این است که راست‌ترین گره در ریشه همیشه از بقیهٔ گره‌ها بزرگتر مساوی خواهد بود و مهمتر از همه اینکه آرایه‌ای که اکنون مرتب شده برای اینکه مجموعهٔ معتبری از پشته‌ها شود نیازی به باز آرایی ندارد. الگوریتم ساده‌است. ما با تقسیم آرایهٔ مرتب نشده به یک پشته از یک عنصر آغاز می‌کنیم.
مثل بخش مرتب نشده. یک آرایهٔ تک عنصر یک دنبالهٔ معتبری از پشته‌ها است. این دنباله بوسیلهٔ اضافه کردن عنصر به راست پشته افزایش می‌یابد (بزرگ می‌شود) و بوسیلهٔ جابجا کردن عناصر (swap) خاصیت دنباله‌ای و خاصیت پشته‌ای حفظ شود. از این نکات می‌فهمیم که راست‌ترین عنصر هر دنباله‌ای از پشته‌ها بزرگترین عنصر آن پشته‌است و بنابراین هر عنصر سر جای اصلی خود قرار دارد
یک لحظه الگوریتم بهینه‌سازی ادسخر دیکسترارا نادیده بگیرید. دو عملیات لازم است. افزایش رشته بوسیله اضافه کردن عنصر به راست اگر مثلاً آخرین ۲ هیپ به سایزهای formula_4و formula_13 باشد عنصر جدیدی که اضافه کنیم گرهٔ ریشهٔ یک هیپ بزرگتر به سایز formula_14 شود که این هیپ لازم ندارد که خاصیت هیپ را داشته باشد. اگر مثلاً آخرین دو هیپ formula_6 متوالی نبودند بعد از راست‌ترین عنصر یک هیپ جدید به سایز ۱ ایجاد می‌شود که در حقیقت این همان formula_21 هست. پس در نتیجه در این حالت راست‌ترین هیپ اکنون سایز formula_21 دارد. بعد از این خصوصیات رشته و هیپ باید ذخیره شود به شکل زیر این کار انجام شود: بهینه‌سازی : اگر هیپ جدید قصد دارد قسمتی از هیپ بزرگتر شود خودتان را برای ایجاد رشتهٔ خصوصیات زحمت ندهید. این کار فقط وقتی لازم است که یک هیپ در دسترس است و تنها کاری که می‌کند سایز نهایی را می‌دهد. بعد از اینکه این کار انجام شد نگاه کنید چگونه بسیاری از عناصر، چپ هیپ جدید به سایز formula_4 هستند حال اگر هیپی با مقدار 1+formula_18 وجود داشت این هیپ ادغام می‌شود. خصوصیات هیپ را در راست‌ترین هیپ ذخیره نکنید، اگر حالا آن هیپ یکی از هیپ‌های نهایی رشته شود سپس خصوصیات رشته را ذخیره کنید. البته هر موقع که یک هیپ چدید ایجاد می‌شود بعد از اضافه شدن، راست‌ترین هیپ جدید از راست‌ترین هیپ قبل بزرگتر نیست و خصوصیات هیپ نیاز دارند ذخیره شوند. کاهش رشته بوسیله حذف راست‌ترین عنصر اگر راست‌ترین عنصر سایز ۱ دارد دیگر هیچ کاری لازم نیست انجام دهید. به سادگی راست‌ترین هیپ را حذف کنید. اگر راست‌ترین هیپ سایز ۱ نداشت سپس ریشه را حذف کنید سپس ۲ هیپ قبلی (sub-heap)را مثل عضوهای رشته نمایش دهید. خصوصیات رشته را ابتدا در چپ‌ترین و سپس در راست‌ترین عنصر ذخیره کنید "بهینه‌سازی" موقعی که خصوصیات رشته را ذخیره می‌کنیم به مقایسهٔ ریشهٔ هیپ چپ با دو گرهٔ بچه هیپی که فقط نمایش داده شده‌است نیاز نداریم زیرا ما می‌دانیم که این هیپ‌ها دارای خصوصیات هستند و فقط آن را با ریشه مقایسه کنیم
در این کد دو متغیر lo وhi به عنوان ۲ کران بالا و پایین استفاده شده است
ویکی‌پدیا  انگلیسیCommented transcription of EWD796ahttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF
http://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html