Resumen: Sorting and searching are among the most important and fundamental concepts in computer science.
There are two basic approaches to sorting: comparison-based methods such as merge sort or quick sort, and key-based methods such as radix sort, which employ the structure of sort keys to organize their workings. The former methods are generic in that they work for arbitrary orders (total preorders). By contrast, the latter are datatype generic: they can be defined by induction over the structure of keys or, more generally, over the structure of order denotations.
Likewise, we can distinguish between comparison-based search methods such as binary search trees and key-based methods such as tries, which employ the structure of search keys to organize information.
Even though comparison-based methods seem to be more popular, key-based methods are vastly superior: sorting runs in time linear in the size of the sort keys, and searching takes time linear in the size of the search key.
In this talk I show how to implement key-based methods for sorting, discrimination, and searching in Haskell, discuss their key properties, and highlight core relations between these algorithms.