qsort Test Program

This predicate sorts a list by the quick sort algorithm developed by C.A.R. Hoare. The algorithm recursively proceeds by splitting the given list into two halves and then sorting each half. In the given benchmark the splitting is simply based on the head of the list. The algorithm has a good average order of O(n log n), but it can have an order of O(n2) in the worst case. The benchmark is already found in D.H.D. Warren’s thesis [2, page 220].

One test iteration will sort a list with 50 numbers.

Kommentare