مرتب سازی کتابخانه ای

مرتب سازی کتابخانه ای یا مرتب سازی درجی شکافدار یک الگوریتم مرتب سازی است که ازمرتب سازی درجی به همراه فضاهای خالی یا همان شکاف ها برای سرعت دادن به فرایند درج یک زیر رشته جدید استفاده می کند. [ ۱]
فرض کنید یک کتابدار می خواهد کتابهایش را بر حسب حروف الفبا در یک قفسه بچیند، به طوری که از حرف الف در سمت چپ شروع می کند به چیدن و به سمت راست می رود تا به حرف ی برسد و در بین حروف هم هیچ فاصله ای نمی گذارد. اگر کتابدار یک کتاب جدید را که باحرف ب شروع می شود را بخواهد در قفسه بگذارد باید اول جای ان را پیدا کند و سپس همه کتابها را از انجا به بعد یکی جلو ببرد تا جا برای کتاب باز شود، ای دقیقاً همان کاری است که در مرتب سازی درجی انجام می دهیم. اگر ما یک فاصله بعد از هر حرف می گذاشتیم نیازی نبود که همهٔ کتاب ها را جلو ببریم و فقط تعداد کمی کتاب را جابجا می کردیم که این ایدهٔ فضای خالی گذاشتن مهمترین اصل مرتب سازی کتابخانه ای است.
این الگوریتم به وسیلهٔ Michael A. Bender، Martín Farach - Colton و Miguel Mosteiro در سال ۲۰۰۶ معرفی شد.
مثل مرتب سازی درجی که به عنوان پایه مرتب سازی کتابخانه ای است، این نوع مرتب سازی از نوع مرتب سازی های مقایسه ای پایدار است و می تواند به عنوان یک الگوریتم ( online ) اجرا شود یعنی نیازی نیست که همهٔ داده ها به ان داده شوند تا کار کند بلکه می تواند از لحظهٔ وارد شدن داده ها کار مرتب سازی داده ها را انجام بدهد. ازمایشات نشان داده که احتمال اجرای این الگوریتم با پیچیدگی زمانی ( o ( nlogn بیشتراز ( quicksort ) است. پیاده سازی این نوع الگوریتم بسیار شبیه لیست پرشی است. تنها مشکل این نوع مرتب سازی استفاده زیاد از حافظه برای ایجاد شکاف ها است.
بدترین پیچیدگی ( o ( n^2
بهترین پیچیدگی ( o ( n
پیچیدگی متوسط ( o ( nlogn