Adaptive sorting: an information theoretic perspective

@article{citeulike:2354932, abstract = {Abstract\ \ We present two algorithms that are near optimal with respect to the number of inversions present in the input. One of the algorithms is a variation of insertion sort, and the other is a variation of merge sort. The number of comparisons performed by our algorithms, on an input sequence of length n that has I inversions, is at most \$\$n\,{\rm log}\_{2} (\frac{I}{n} + 1) + O(n)\$\$ . Moreover, both algorithms have implementations that run in time \$\$O(n\,{\rm log}\_{2} (\frac{I}{n} + 1)\,+\,n)\$\$ . All previously published algorithms require at least \$\$cn\,{\rm log}\_{2} (\frac{I}{n} + 1)\$\$ comparisons for some c\ \> 1.}, author = {Elmasry, Amr and Fredman, Michael }, citeulike-article-id = {2354932}, doi = {10.1007/s00236-007-0061-0}, journal = {Acta Informatica}, keywords = {algorithms, complexity, information}, month = {February}, number = {1}, pages = {33--42}, posted-at = {2008-02-08 21:53:47}, priority = {2}, title = {Adaptive sorting: an information theoretic perspective}, url = {http://dx.doi.org/10.1007/s00236-007-0061-0}, volume = {45}, year = {2008} }

TY - JOUR ID - citeulike:2354932 L3 - citeulike-article-id:2354932 TI - Adaptive sorting: an information theoretic perspective JF - Acta Informatica VL - 45 IS - 1 SP - 33 EP - 42 N2 - Abstract  We present two algorithms that are near optimal with respect to the number of inversions present in the input. One of the algorithms is a variation of insertion sort, and the other is a variation of merge sort. The number of comparisons performed by our algorithms, on an input sequence of length n that has I inversions, is at most $$n\,{\rm log}_{2} (\frac{I}{n} + 1) + O(n)$$ . Moreover, both algorithms have implementations that run in time $$O(n\,{\rm log}_{2} (\frac{I}{n} + 1)\,+\,n)$$ . All previously published algorithms require at least $$cn\,{\rm log}_{2} (\frac{I}{n} + 1)$$ comparisons for some c > 1. KW - algorithms KW - complexity KW - information AU - Elmasry, Amr AU - Fredman, Michael PY - 2008/02/19/ UR - http://dx.doi.org/10.1007/s00236-007-0061-0 ER -