Library sort - Revision history

Sulhan: /* Pseudocode */ : remove trailing ")"

2025-01-19T10:17:40Z

Pseudocode: : remove trailing ")"

← Previous revision		Revision as of 10:17, 19 January 2025
Line 52:		Line 52:

	'''for''' i ← 1 to floor(log2(n-1)) '''do'''		'''for''' i ← 1 to floor(log2(n-1)) '''do'''
	rebalance(S, 1, 2^(i-1)))		rebalance(S, 1, 2^(i-1))
	'''for''' j ← 2^(i-1) to 2^i '''do'''		'''for''' j ← 2^(i-1) to 2^i '''do'''
	ins ← binarysearch(A[j], S, 2^i)		ins ← binarysearch(A[j], S, 2^i)

Geysirhead: removed Category:Sorting algorithms using HotCat redundant

2023-11-01T18:39:02Z

removed Category:Sorting algorithms using HotCat redundant

← Previous revision		Revision as of 18:39, 1 November 2023
Line 67:		Line 67:
	{{sorting}}		{{sorting}}

	[[Category:Sorting algorithms]]
	[[Category:Comparison sorts]]		[[Category:Comparison sorts]]
	[[Category:Stable sorts]]		[[Category:Stable sorts]]

Tamfang: /* top */ comma unnecessary/unbalanced

2023-08-29T15:12:29Z

top: comma unnecessary/unbalanced

← Previous revision		Revision as of 15:12, 29 August 2023
Line 11:		Line 11:
	\|optimal=?		\|optimal=?
	}}		}}
	'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:		'''Library sort''' or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
	<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>		<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

Tc14Hd at 10:10, 1 August 2023

2023-08-01T10:10:27Z

← Previous revision		Revision as of 10:10, 1 August 2023
Line 1:		Line 1:
			{{Short description\|Sorting algorithm}}
	{{refimprove\|date=October 2017}}		{{refimprove\|date=October 2017}}
	{{Infobox Algorithm		{{Infobox Algorithm

Muf99: /* Pseudocode */ Added the rebalancing operations and fixed some of the indexing

2023-04-14T21:48:41Z

Pseudocode: Added the rebalancing operations and fixed some of the indexing

← Previous revision		Revision as of 21:48, 14 April 2023
Line 38:		Line 38:
	'''procedure''' rebalance(A, begin, end) '''is'''		'''procedure''' rebalance(A, begin, end) '''is'''
	r ← end		r ← end
	w ← end ÷ 2		w ← end × 2

	'''while''' r ≥ begin '''do'''		'''while''' r ≥ begin '''do'''
⚫	A[w+1] ← gap
	A[w] ← A[r]		A[w] ← A[r]
		⚫	A[w-1] ← gap
	r ← r − 1		r ← r − 1
	w ← w − 2		w ← w − 2
Line 50:		Line 50:
	S ← new array of n gaps		S ← new array of n gaps

	'''for''' i ← 1 to floor(log2(n~~) +~~ 1) '''do'''		'''for''' i ← 1 to floor(log2(n-1)) '''do'''
	~~'''for'''~~ ~~j ← 2^i to~~ 2^(i + 1) ~~'''do'''~~		rebalance(S, 1, 2^(i-1)))
	~~ins~~ ← ~~binarysearch~~(~~A[j],~~ S, 2^(i ~~− 1))~~		'''for''' j ← 2^(i-1) to 2^i '''do'''
			ins ← binarysearch(A[j], S, 2^i)
	insert A[j] at S[ins]		insert A[j] at S[ins]

Tamfang: /* top */ in what language was this first written?

2023-03-28T18:54:52Z

top: in what language was this first written?

← Previous revision		Revision as of 18:54, 28 March 2023
Line 17:		Line 17:
	Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.		Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.

	Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would depend on implementation. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the ~~with-~~high-probability time bounds, it ~~requires to~~ randomly permute the input, ~~what~~ changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take ~~profit~~ of presorted input.		Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would depend on implementation. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the high-probability time bounds, it must randomly permute the input, which changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take advantage of presorted input.

	Another drawback is that it cannot be run as an [[online algorithm]], because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour.		Another drawback is that it cannot be run as an [[online algorithm]], because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour.

	One weakness of [[insertion sort]] is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but is also ~~adding~~ an extra cost in the rebalancing step. In addition, locality of reference will be poor compared to [[mergesort]] as each insertion from a random data set may access memory that is no longer in cache, especially with large data sets.		One weakness of [[insertion sort]] is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but also adds an extra cost in the rebalancing step. In addition, locality of reference will be poor compared to [[mergesort]], as each insertion from a random data set may access memory that is no longer in cache, especially with large data sets.

	==Implementation==		==Implementation==

Tamfang: /* top */ plainer words

2023-03-28T18:52:33Z

top: plainer words

← Previous revision		Revision as of 18:52, 28 March 2023
Line 17:		Line 17:
	Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.		Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.

	Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would be ~~implementation~~ ~~dependent~~. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the with-high-probability time bounds, it requires to randomly permute the input, what changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take profit of presorted input.		Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would depend on implementation. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the with-high-probability time bounds, it requires to randomly permute the input, what changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take profit of presorted input.

	Another drawback is that it cannot be run as an [[online algorithm]], because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour.		Another drawback is that it cannot be run as an [[online algorithm]], because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour.

Citation bot: Alter: template type. Add: s2cid, eprint. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 1696/1776

2022-01-30T18:24:36Z

Alter: template type. Add: s2cid, eprint. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 1696/1776

← Previous revision		Revision as of 18:24, 30 January 2022
Line 13:		Line 13:
	<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>		<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

	The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite ~~arxiv~~ \|~~arxiv~~=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>		The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arXiv \|eprint=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| s2cid=14701669 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>

	Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.		Like the insertion sort it is based on, library sort is a [[comparison sort]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n<sup>2</sup>). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality.

AllenDowney: typo

2021-09-13T13:15:30Z

typo

← Previous revision		Revision as of 13:15, 13 September 2021
Line 11:		Line 11:
	}}		}}
	'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:		'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
	<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they ~~finds~~ the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>		<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

	The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arxiv \|arxiv=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>		The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arxiv \|arxiv=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>

AllenDowney: Replacing "he" with singular "they"

2021-09-13T13:14:41Z

Replacing "he" with singular "they"

← Previous revision		Revision as of 13:14, 13 September 2021
Line 11:		Line 11:
	}}		}}
	'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:		'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
	<blockquote>Suppose a librarian were to store ~~his~~ books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once he finds the correct space in the B section, he will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if he were to leave a space after every letter, as long as there was still space after B, he would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>		<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they finds the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

	The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arxiv \|arxiv=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>		The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arxiv \|arxiv=cs/0407003 \|title=Insertion Sort is O(n log n) \|date=1 July 2004 \|last1=Bender \|first1=Michael A. \|last2=Farach-Colton \|first2=Martín \|authorlink2=Martin Farach-Colton \|last3=Mosteiro \|first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal \| journal=Theory of Computing Systems \| volume=39 \| issue=3 \| pages=391–397 \| date=June 2006 \| last1=Bender \| first1=Michael A. \| last2=Farach-Colton \| first2=Martín \| authorlink2=Martin Farach-Colton \| last3=Mosteiro \| first3=Miguel A. \| title=Insertion Sort is O(n log n) \| doi=10.1007/s00224-005-1237-z \| url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| arxiv=cs/0407003 \| access-date=2017-09-07 \| archive-url=https://web.archive.org/web/20170908070035/http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf \| archive-date=2017-09-08 \| url-status=dead }}</ref>