module Shellsort where

import Data.List (transpose, insert, unfoldr)

-- | Shellsort

shellsort :: (Ord a) => [a] -> [a]

shellsort xs = foldr (decolumnize (map (foldr insert []))) xs gaps

where

gaps = takeWhile (< length xs) sedgewick

sedgewick = concat [[9 * 2^n - 9 * 2^(n `div` 2) + 1, 8 * 2^(n+1) - 6 * 2^(n `div` 2) + 1] | n <- [0..]]

decolumnize f k = concat . transpose . f . transpose . takeWhile (not . null) . unfoldr (Just . splitAt k)

main :: IO ()

main = do

let arr = [12,1,6,31,99,25,3,56,21,6]

putStr "The sorted version of the array is "

print (shellsort arr)