5.3. Sorting in Linear Time

• File: LinearTimeSorting.ml

As we have just determined, one cannot do comparison-based sorting better than in \(O(n \log n)\) in the worst case. However, we can improve this complexity if we base the logic of our algorithm not just on comparisons, but will also exploit the intrinsic properties of the data used as keys for elements to be sorted (e.g., integers). In this chapter we will see some examples of such specialised sorting procedures.

5.3.1. Simple Bucket Sort

Bucket sort works well for the case, when the size of the set, from which we draw the keys is limited by a certain number bnum. In this case, we can allocate an auxiliary array of “buckets” (implemented as lists), which will serve to collect elements with the key corresponding to the bucket number. The code is as follows:

let simple_bucket_sort bnum arr =
  let buckets = Array.make bnum [] in
  let len = Array.length arr in
  for i = 0 to len - 1 do
    let key = fst arr.(i) in
    let bindex = key mod bnum in
    let b = buckets.(bindex) in
    buckets.(bindex) <- arr.(i) :: b
  done;
  let res = ref [] in
  for i = bnum - 1 downto 0 do
    res := List.append (List.rev (buckets.(i))) !res
  done;
  list_to_array !res

Having created an array buckets, the sort than traverses the initial array arr, and puts each element with a key key into the bucket with the corresponding index, obtained as bindex = key mod bnum. Notice that if the all keys are in range limited by bnum, the mod operation returns the key itself.

Therefore, the first for-loop has a complexity \(\Theta(n)\), where \(n\) is the size of arr. The second loop walks through the array of buckets all the buckets (making bnum iterations) and concatenates all the lists, returning the result as the array. It is straightforward to show that the resulting complexity of the algorithm is in \(O(\mathtt{bnum} \cdot n)\) (it can be made \(O(\mathtt{bnum} + n)\) if we use append-only buffers, so we don’t have to re-traverse the lists), i.e., it is linear in n.

We can see simple_bucket_sort in action:

# let c =[|9; 9; 0; 9; 4; 7; 9; 2; 3; 3|];;

# simple_bucket_sort 10 c;;
  - : int array = [|0; 2; 3; 3; 4; 7; 9; 9; 9; 9|]

5.3.2. Enhanced Bucket Sort

If the size of the space of keys exceeds the number of the buckets, one can still use the same idea, while also sorting each bucket individually with a suitable sorting, such as insertion sort (implemented for lists), as it will be operating on small and almost sorted sub-arrays:

let bucket_sort max ?(bnum = 1000) arr =
  let buckets = Array.make bnum [] in
  let len = Array.length arr in
  for i = 0 to len - 1 do
    let key = arr.(i) in
    let bind = key * bnum / max in
    let b = buckets.(bind) in
    buckets.(bind) <- arr.(i) :: b
  done;
  let res = ref [] in
  for i = bnum - 1 downto 0 do
    let bucket_contents = List.rev (buckets.(i)) in
    let sorted_bucket = InsertSort.insert_sort bucket_contents in
    res := List.append sorted_bucket !res
  done;
  list_to_array !res

The code of bucket_sort above takes an optional parameter bnum for the number of buckets (default is 10, if omitted) and a parameter max to indicate the maximal possible key (should be guessed by the client of the sorting). When allocating elements to the corresponding buckets, it divides the entire space of keys (up to the maximal one) into bnum portions, and puts the corresponding element into the appropriate bucket. Since elements with different keys (from the same segment) may end up in the same bucket, and additional sorting is required. Let us test this implementation:

# let e = generate_int_array 10000;;
val e : int array = [|4505; 6905; 5076; 9250; 5101; 2539; 1721; ... |]

# bucket_sort 10000 e;;
- : int array = [|0; 1; 3; 3; 5; 5; 5; 6; 6; 9; 10; ... |]

5.3.3. Stability of sorting

An important property of a sorting algorithm is stability. A sorting algorithms is stable if it preserves the ordering between the elements with equal keys in the initial array.

An example of a stable sorting algorithm is kv_bucket_sort shown below, which sorts an array of key-value pairs based on the keys:

let kv_bucket_sort bnum arr =
  let buckets = Array.make bnum [] in
  let len = Array.length arr in
  for i = 0 to len - 1 do
    let key = fst arr.(i) in
    let bindex = key mod bnum in
    let b = buckets.(bindex) in
    buckets.(bindex) <- arr.(i) :: b
  done;
  let res = ref [] in
  for i = bnum - 1 downto 0 do
    res := List.rev_append buckets.(i) !res
  done;
  list_to_array !res

As an example, consider its following execution:

# let f = [|(3, "zqped"); (8, "esmup"); (7, "tvqej"); (8, "xhlzj"); (4, "blann");
            (9, "ouors"); (0, "iocvx"); (3, "dacht"); (7, "rncpn");
            (7, "khott")|];;

# kv_bucket_sort 10 f;;
- : (int * string) array =
[|(0, "iocvx"); (3, "zqped"); (3, "dacht"); (4, "blann"); (7, "tvqej");
  (7, "rncpn"); (7, "khott"); (8, "esmup"); (8, "xhlzj"); (9, "ouors")|]

The initial array has elements (7, "rncpn") and (7, "khott") in this very order. In the same order, the appear in the resulting array. Other stable sorting algorithm is insertion sort. Not all sorting algorithms are stable though. Try to answer, whether merge sort is stable? What about Quicksort?

5.3.4. Radix Sort

The stability comes into play, when one sorting algorithm uses another one as a black-box, relying on the fact that original order of elements in partially-sorted arrays with “almost-same” keys will be preserved.

As an example, radix sort is a linear-time sorting, building on the idea of bucket-sort, but making it scale logarithmically, which is necessary if the space of possible keys is too large (e.g., comparable with the length of an array, in which case bucket sort’s complexity becomes quadratic). It makes use of bucket sort as its component, applying it iteratively and sorting a list of integer-keyed elements per key digit, startgin from the smallest register:

let radix_sort arr =
  let len = Array.length arr in
  let max_key =
    let res = ref 0 in
    for i = 0 to len - 1 do
      if arr.(i) > !res
      then res := arr.(i)
    done; !res
  in
  if len = 0 then arr
  else
    let radix = ref max_key in
    let ls = array_to_list arr in
    let combined = list_to_array (list_zip ls ls) in
    let res = ref combined in
    while !radix > 0 do
      res := kv_bucket_sort 10 !res;
      for i = 0 to len - 1 do
        let (k, v) = !res.(i) in
        !res.(i) <- (k / 10, v)
      done;
      radix := !radix / 10
    done;
    let result_list = array_to_list !res in
    list_to_array result_list |> Array.map snd

It starts by determining the largest key max_key in the initial array. Next, it creates an array combined, which pairs all elements in the original array with their keys. In the while loop, it sorts elements, using kv_bucket_sort, based on their digit. It starts from the lowest register, and then keeps dividing the key component of each element, “attached” for the sorting purposes, by 10, repeating the bucket sort, until it runs out of registers.

How many iterations the while-loop will make? Notice that each time it divides the key space by 10, so it will only run for \(\log_{10}( \mathtt{max\_key})\) iterations. This determines the complexity of the radix sort, which is, therefore \(O(n \log(\mathtt{max\_key}))\), i.e., it is linear if max_key is considered as a constant.

One can test the implementation of radix sort as follows:

let%test "radix-sort" =
  let a = generate_int_array 1000 in
  let b = radix_sort a in
  array_sorted b &&
  same_elems (array_to_list a) (array_to_list b)