This post describes the implementation of the **Dutch partition** problem using OCaml
such that the memory space complexity is constant.

## Description

The Dutch partition arises when we want to optimize the quick sort: given
an array `A`

whose elements are comparable and an index `i`

of an element in the
array. Reorder the array such that the initial elements are smaller than `A[i]`

,
and are followed by elements that equal to `A[i]`

, the final elements are bigger
than `A[i]`

, using constant memory space complexity \(O(1)\).

I implement the problem using OCaml. The main idea is the use of 3 flags to determine the 3 regions above.

`A[0 .. smaller-1]`

: smaller region`A[smaller .. equivalent-1]`

: equivalent region`A[equivalent .. larger]`

: unclassified region`A[larger+1 .. size-1]`

: larger region

The “smaller” and “equivalent” flags are initialized 0 and “larger” is
initialized `(size - 1)`

. That means at the beginning the whole array is
unclassified. We use a recursive function to reduce the number of
elements in unclassified region is 0.

## Code

The source code is given as follows.

```
let swap i j a =
try
let tmp = a.(j) in
a.(j) <- a.(i);
a.(i) <- tmp; a
with
_ -> raise (Invalid_argument "out-of-range")
(* auxiliary function *)
(* a[0 .. smaller - 1] : smaller region
a[smaller .. equivalent - 1] : equivalent region
a[equivalent .. larger] : unclassified region
a[larger + 1 ... size - 1] : larger region
*)
let rec partition smaller equivalent larger pivot a =
if equivalent <= larger then
begin
try
if a.(equivalent) < pivot then
(* put a.(equivalent) to the smaller region *)
partition (smaller+1) (equivalent+1) larger pivot (swap smaller equivalent a)
else
if a.(equivalent) = pivot then
(* move to the next element in the unclassified region *)
partition smaller (equivalent+1) larger pivot a
else
(* move a.(equivalent) to the larger region *)
partition smaller equivalent (larger-1) pivot (swap equivalent larger a)
with
_ -> raise (Invalid_argument "out-of-range")
end
else
a
let dutch_partition pivot_index a =
try
partition 0 0 (pred (Array.length a)) (a.(pivot_index)) a
with
_ -> raise (Invalid_argument "out-of-range")
open Printf
(* test *)
let _ =
Array.iter (printf "%d; ") (dutch_partition 3 [|0;1;9;9;9;9;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19|])
```