Quick Sort: Mutable or ST Array
Mutability, ST and pure code

Whenever you can use ST instead of IO use ST. ST limits the effects that can happen, and runST (or its variants) make sure that no STRefs (or variants) leave the ST. That is, you can always embed a ST s a where you want to use a. You cannot do the same for IO a.

Unfortunately, update has \$\mathcal O(n+m) \$, and therefore every call of swap is \$\mathcal O(n) \$. That's not a problem when you have a single Vector, e.g.

V.foldr (\x a -&gt; x + 2 * a) 0 . V.map sin . (// foo) . fromList


will generate a single vector due to fusion, not three intermediates. Depending on the used vector version and optimization level, you might even end up with a single loop and no generated vector at all. So immutability doesn't prevent optimizations.

Quick Sort on the other hand really needs mutability. So a ST variant (STUArray or MVector) is more appropriate.

Interface

Now that we know that it's fine to use an ST variant, let's have a look at your code. First we look at qsort's type:

qsort :: (IOArray Int Int) -&gt; Int -&gt; Int -&gt; IO ()


An end user has no idea what Int and Int shall be. They want to sort an array, not ponder the right arguments. Therefore, we add a variant that doesn't use that arguments:

import Control.Monad
import Control.Monad.ST
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as M

sort  :: Ord a =&gt; V.Vector a -&gt; V.Vector a
sort v = -- left as exercise, should use sort'

sort' :: Ord a =&gt; M.STVector s a -&gt; ST s ()
sort' v = qsort v 1 (M.length v)


This interface is easy to use and hard to get wrong. I use the vector variants since I'm more familiar with those, but the same holds for STArray. Note that I relaxed the Int to Ord a => a`.

Internals

Next, we have a look at qsort itself. I'll keep its type for now. First of, instead of 

if condition then return () else action


use

when (not condition) action


After all, return does not return prematurely, which can be misleading to Haskell newcomers. Next, try not to shadow Prelude names like min and max. Let's call the arguments lower and upper instead. 

Furthermore, you call the value at an index arr_idx. That's misleading. And p is usually used as predicate, so let's call it piv instead. And final_i is just the new midpoint we found with our piv. We end up with.

qsort :: Ord a =&gt; (IOArray Int a) -&gt; Int -&gt; Int -&gt; IO ()
qsort arr lower upper =
    when (upper - lower &gt;= 1) $ do
        piv &lt;- readArray arr lower
        midpoint &lt;- foldM (partitioner p) (lower+1) [(lower+1)..upper]
        swap lower $ midpoint - 1
        qsort arr lower   (midpoint - 2)
        qsort arr final_i upper
    where
        swap i j = do
            arr_i &lt;- readArray arr i
            arr_j &lt;- readArray arr j
            writeArray arr i arr_j
            writeArray arr j arr_i

        partitioner piv i idx = do
            value &lt;- readArray arr idx
            if value &gt; piv then
                return i
            else do
                swap i idx
                return $ i+1


Exercise: Try to rewrite qsort with M.Vector or even Data.Vector.Unboxed.Mutable (the latter only needs an additional constraint). 

Bottom line

Other than that your mutable code looks fine. I would change swap slightly so that there is only one temporary element, though:

        swap i j = do
            tmp &lt;- readArray arr i
            readArray arr j &gt;&gt;= writeArray arr i
            writeArray arr j tmp


That's personal preference.