Sorting an array

There's an array of values from 1 to n. It isn't sorted. We have to sort it, but there are only to ways to move: third element to beginning or last element to beginning. How to do that ?

Here's a brute force solution. Generate every possible sequence of moves and filter out the move sequences that don't sort the list. Lists of even length are sortable, but some odd lists aren't sortable.


{-#LANGUAGE ViewPatterns #-}

import Prelude hiding (length, splitAt)
import Data.List (permutations)
import Data.Sequence hiding (filter)

herpsort :: (Ord a) => Seq a -> Seq a
herpsort s = head . filter sorted . map (runMoves s) $ allMoves

runMoves :: Seq a -> [Seq a -> Seq a] -> Seq a
runMoves s moves = foldr ($) s moves

allMoves :: [[Seq a -> Seq a]]
allMoves =
    allMoves' [[moveThird], [moveLast]]
  where
    allMoves' s = s ++ allMoves' (map (moveThird :) s ++ map (moveLast :) s)

moveThird s = moveToFront 2 s
moveLast  s = moveToFront (length s - 1) s

moveToFront :: Int -> Seq a -> Seq a
moveToFront n s =
    (item >< first) >< rest
  where
    (first, xs)  = splitAt n s
    (item, rest) = splitAt 1 xs

sorted :: (Ord a) => Seq a -> Bool
sorted (viewl -> EmptyL)  = True
sorted (viewl -> x :< xs) =
    sorted' x xs
  where
    sorted' :: (Ord a) => a -> Seq a -> Bool
    sorted' prev (viewl -> EmptyL)  = True
    sorted' prev (viewl -> x :< xs) = prev <= x && sorted' x xs



test1 = map herpsort . map fromList . permutations $ [1..4]
test2 = map herpsort . map fromList . permutations $ [1..6]

-- not sortable
hurr = herpsort $ fromList [2, 1, 3, 4, 5]

-- sortable
durr = herpsort $ fromList [2, 1, 3, 5, 4]

-- not sortable
hurf = herpsort $ fromList [2, 1, 3, 4, 5, 6, 7]

-- sortable
durf = herpsort $ fromList [2, 1, 3, 4, 5, 7, 6]