-- qsort :: Array -> beginning of subsection -> end of subsection ->
--      index of first square gt pivot -> index of next unpartitioned point
qsort :: (IOArray Int Int) -> Int -> Int -> IO ()
qsort arr min mx =
    if mx - min < 1 then do
        return ()

    else do
        p <- readArray arr min
        --foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
        final_i <- foldM (partitioner p) (min+1) [(min+1)..mx]
        swap min $ final_i - 1
        qsort arr min     (final_i-2)
        qsort arr final_i mx

    where
        swap i j = do
            arr_i <- readArray arr i
            arr_j <- readArray arr j
            writeArray arr i arr_j
            writeArray arr j arr_i

        partitioner p i idx = do
            arr_idx <- readArray arr idx
            if arr_idx > p then
                return i
            else do
                swap i idx
                return $ i+1