مرتب سازی درونگرا

مرتب سازی درونگرا، یک الگوریتم جستجو است که توسط دیوید ماسر ( David Musser ) در سال ۱۹۹۷ طراحی شد. این الگوریتم ابتدا با فراخوانی مرتب سازی سریع شروع کرده و هنگامی بخش بازگشتی مرتب سازی سریع به عمق مشخصی که متناسب با لگاریتم تعداد عناصر موجود است رسید، الگوریتم مرتب سازی هرمی را فراخوانی می کند. این گونه پیاده سازی باعث می شود که الگوریتم هم سرعت زیاد مرتب سازی سریع را روی داده های معمولی داشته باشد و هم بدترین زمان اجرای آن O ( n l o g n ) باشد. در الگوریتم مرتب سازی سریع یکی از مهم ترین مراحل انتخاب نقطه محور ( Pivot Element ) می باشد که عناصر درون آرایه حول آن بخش بندی می شوند. ساده ترین الگوریتم انتخاب نقطه محور، انتخاب اولین یا آخرین عنصر آرایه است که باعث می شود الگوریتم برای آرایه های مرتب زمان اجرای بدی داشته باشد. الگوریتم های دیگری نیز مانند میانه ۳ ( median - of - ۳ ) وجود دارند، اما آن ها هم در بدترین حالت زمان اجرای ( O ( n² خواهند داشت. این نوع ورودی ها می توانند هنگام حمله های انکار سرویس در اینترنت به کار روند. شبه کد الگوریتم با بخش بندی میانه ۳ به صورت زیر می باشد: