Shellsort with three increments
| dc.creator | Janson, Svante | |
| dc.creator | Knuth, Donald E. | |
| dc.date | 1996-08-22 | |
| dc.date.accessioned | 2026-07-07T09:12:20Z | |
| dc.date.available | 2026-07-07T09:12:20Z | |
| dc.description | A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments $(h,g,1)$. In particular, when $h=Θ(n^{7/15})$ and $g=Θ(h^{1/5})$, the average running time is $O(n^{23/15})$. The proof involves interesting properties of the inversions in random permutations that have been $h$-sorted and $g$-sorted. | |
| dc.identifier | https://arxiv.org/abs/cs/9608105 | |
| dc.identifier | http://arxiv.org/abs/cs/9608105 | |
| dc.identifier | Random Structures Algorithms 10 (1997), no. 1-2, 125--142 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151988 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Shellsort with three increments | |
| dc.type | text |