مرتب‌سازی کند

مرتب‌سازی کند (به انگلیسی: Slowsort) نوعی الگوریتم مرتب‌سازی است که جنبهٔ شوخی داشته و کاربردی نمی‌باشد. این الگوریتم بر مبنای قاعده ضرب و تسلیم (کنایه به تقسیم و غلبه) عمل می‌کند. این الگوریتم در سال ۱۹۸۶ توسط آندره برودر و جورج استولفی ابداع شد.

الگوریتم 
مرتب‌سازی کند یک الگوریتم بازگشتی است.

شبه کد پیاده‌سازی درجای آن به صورت زیر می‌باشد:

  procedure slowsort(A,i,j)
  if i>= j then return
  m := ⌊(i+j)/2⌋
  slowsort(A,i,m)                                    // (1.1)
  slowsort(A,m+1,j)                                  // (1.2)
  if A[j] <A[m] then swap A[j] and A[m]             // (1.3)
  slowsort(A,i,j-1)                                  // (2)

 مرتب‌سازی قسمت اول به صورت بازگشتی (۱٫۱)
 مرتب‌سازی قسمت دوم به صورت بازگشتی (۲٫۲)
 یافتن بیشینه کل آرایه با استفاده از مقایسه نتایج ۱٫۱ و ۲٫۲ و قرار دادن این عنصر در انتهای آرایه (۱٫۳)
 مرتب‌سازی کل آرایه به جز عنصر بیشینهٔ پیدا شده مرحلهٔ ۱٫۳ به صورت بازگشتی

پیاده‌سازی این الگوریتم در هسکل (یه صورت تابعی خالص) به صورت زیر است.
  
slowsort :: Ord a => [a] -> [a]
  slowsort xs
  | length xs <= 1 = xs
  | otherwise      = slowsort xsnew ++ [max llast rlast] -- (2)
  where
  l     = slowsort $ take m xs -- (1.1)
  r     = slowsort $ drop m xs -- (1.2)
  llast = last l
  rlast = last r
  xsnew = init l ++ min llast rlast: init r
  m     = fst (divMod (length xs) 2)

پیچیدگی زمانی 
زمان اجرای مرتب‌سازی کند برابر با  می‌باشد؛ بنابراین به ازای هر  ,  از مرتبه زمانی
 for any  می‌باشد؛ بنابراین مرتبه زمانی مرتب‌سازی کتد چند جمله ای نیست و حتی در بهترین حالت بدتر از مرتب‌سازی جبابی است.

منابع 

الگوریتم‌های مرتب‌سازی
شوخی‌های رایانه