Bucket sort assumes input generated by a random process that distributes elements uniformly over the interval *[0, 1)*.

The idea of bucket sort is to divide *[0, 1)* into *n* equal-sized subintervals or *buckets*, and then distribute the *n* input numbers into the buckets. To produce the output, sort the numbers in each bucket and then go through the buckets in order. Sorting a bucket can be done with insertion sort.

```
let rec insert x = function
| [] -> [x]
| h :: tl as ls ->
if x < h then x :: ls else h :: insert x tl
let rec insertion_sort = function
| [] | [_] as ls -> ls
| h :: tl -> insert h (insertion_sort tl)
```

This code for bucket sort assumes the input is an *n*-element array `a`

and that each element *0 ≤ a.(i) < 1*. The code requires an auxillary array

`b`

.(*0 .. n - 1*) of lists (buckets).

```
let bucket_sort a =
let n = Array.length a in
let b = Array.make n [] in
Array.iter
(fun x ->
let i =
int_of_float (
floor (float_of_int n *. x)
) in
Array.set b i (x :: Array.get b i)
) a;
Array.iteri
(fun i l ->
Array.set b i (insertion_sort l)
) b;
Array.fold_left (fun acc bucket -> acc @ bucket) [] b
;;
bucket_sort [| 0.78; 0.17; 0.39; 0.26; 0.72; 0.94
; 0.21; 0.12; 0.23; 0.68|]
```

Bucket sort runs in linear time on the average.

References:

[1] "Introduction to Algorithms" Section 9.4:Bucket Sort -- Cormen et. al. (Second ed.) 2001.