The price of naturalness or how to beat quick sort.
Boris Leonidovich Faifel, Yri Gagarin State Technical Universty of Saratov
Abstract
It is shown that elementary natural insertion sort can be faster than the famous Hoare quicksort. Computational experiments show that when the number of inversions in the array being sorted is 10% or less, insertion sort "overtakes" quick sort.
Speaker
Boris Leonidovich Faifel
Yri Gagarin State Technical Universty of Saratov
Russia
Discussion
Ask question