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

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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

44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)

Cambridge, Massachusettes

October 11-October 14

ISBN: 0-7695-2040-5

	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

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

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.