Michael A. Bender

Professor and David R. Smith Leading Scholar in Computer Science

Department of Computer Science
Stony Brook University

In my very first programming course in computer science, we learned that insertion sort runs in $O(n^2)$ time---each insertion into the array takes time $O(n)$ and there are $n$ insertions.

I distinctly remember asking, "why not leave gaps in the array in anticipation of future insertions?"  Some years later, I would find the answer this question---adding gaps to insertion sort actually does work, giving another natural $O(n\log n)$ algorithm called ``library sort''.

This technique of strategically leaving gaps in an array to accommodate future insertions has now made a surprising number of recurrences throughout my career.  In addition to library sort, I'll explain two recent and much more sophisticated results: how we (1) overturned a 60-year-old conventional wisdom about how fast linear probing runs, and (2) disproved a 30-year-old conjecture on how efficiently one can keep a dynamic set of sorted items in an array.

Michael A. Bender

Professor and David R. Smith Leading Scholar in Computer Science

Department of Computer Science
Stony Brook University

In my very first programming course in computer science, we learned that insertion sort runs in $O(n^2)$ time---each insertion into the array takes time $O(n)$ and there are $n$ insertions.

I distinctly remember asking, "why not leave gaps in the array in anticipation of future insertions?"  Some years later, I would find the answer this question---adding gaps to insertion sort actually does work, giving another natural $O(n\log n)$ algorithm called ``library sort''.

This technique of strategically leaving gaps in an array to accommodate future insertions has now made a surprising number of recurrences throughout my career.  In addition to library sort, I'll explain two recent and much more sophisticated results: how we (1) overturned a 60-year-old conventional wisdom about how fast linear probing runs, and (2) disproved a 30-year-old conjecture on how efficiently one can keep a dynamic set of sorted items in an array.