An In-Place Sorting with O(n log n) Comparisons and O(n) Moves

Cambridge, Massachusettes October 11-October 14

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238198

44th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Gianni Franceschini Articles by Viliam Geffert

	ASCII Text	x
	Gianni Franceschini, Viliam Geffert, "An In-Place Sorting with O(n log n) Comparisons and O(n) Moves," Foundations of Computer Science, Annual IEEE Symposium on, pp. 242, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.

	BibTex	x
	@article{ 10.1109/SFCS.2003.1238198, author = {Gianni Franceschini and Viliam Geffert}, title = {An In-Place Sorting with O(n log n) Comparisons and O(n) Moves}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2003}, issn = {0272-5428}, pages = {242}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238198}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - An In-Place Sorting with O(n log n) Comparisons and O(n) Moves SN - 0272-5428 SP EP A1 - Gianni Franceschini, A1 - Viliam Geffert, PY - 2003 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Gianni Franceschini, University of Pisa

Viliam Geffert, P. J. Šafárik University

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports.

This solves a long-standing open problem, stated explicitly, e.g., in [J. I. Munro and V. Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

Citation:

Gianni Franceschini, Viliam Geffert, "An In-Place Sorting with O(n log n) Comparisons and O(n) Moves," focs, pp.242, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.