Computer Science Department
School of Computer Science, Carnegie Mellon University
Umut A. Acar, Guy E. Blelloch, Robert Harper
We study the technique in the context of a purely functional language, called IFL, and as an ML library. The library provides an efficient implementation of our techniques with constant overhead. As examples, we consider Quicksort and Insertion Sort. We show that Quicksort handles insertions or deletions at random positions in the input list in O(log n) expected time. For insertion sort, we show that insertions and deletions anywhere in the list take O(n) time.