Sorting methods for small arrays, with C. C. Ribeiro. PUC-Rio Department of Informatics Technical Report MCC 23-00, 2000.

Abstract: We present and compare four efficient quadratic, comparison-based algorithms for small arrays and (for three of them) almost sorted inputs. In addition to the well-known insertion sort and selection sort, we analyze 2-insertion sort (a variation of insertion sort) and stacksort (based on selection sort). We show that the new algorithms perform fewer comparisons on average than their original versions. The theoretical analysis is confirmed by experimental data, which include promising results concerning the use of 2-insertion sort in conjunction with quicksort.