Sorting algorithm - Revision history

2001:610:450:A0:0:0:0:2A: Placed "recombinant sort" in the table of non-comparison methods; fixed some of the complexity terms following the paper, but I am unsure about it. Small changes to its paragraph to make it more neutral.

2025-04-23T12:59:28Z

Placed "recombinant sort" in the table of non-comparison methods; fixed some of the complexity terms following the paper, but I am unsure about it. Small changes to its paragraph to make it more neutral.

@@ Line 348: / Line 348: @@
 | Selection
 | align="left" | In-place with theoretically optimal number of writes.
 |}
@@ Line 481: / Line 470: @@
 | {{No}}
 |align="left"| A variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.
 |}
@@ Line 646: / Line 645: @@
 ==== Recombinant sort ====
-Recombinant sort is a novel non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm represents a synergetic combination of bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers. Unlike many traditional sorting algorithms, it maintains consistent linear performance across various input distributions.<ref>{{citation |url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 |title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort|date=2020 |doi=10.18280/isi.250513 |last1=Kumar |first1=Peeyush |last2=Gangal |first2=Ayushe |last3=Kumari |first3=Sunita |journal=Ingénierie des Systèmes D Information |volume=25 |issue=5 |pages=655–668 |arxiv=2107.01391 }}</ref>
+Recombinant sort is a non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm combines bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers.<ref>{{citation |url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 |title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort|date=2020 |doi=10.18280/isi.250513 |last1=Kumar |first1=Peeyush |last2=Gangal |first2=Ayushe |last3=Kumari |first3=Sunita |journal=Ingénierie des Systèmes D Information |volume=25 |issue=5 |pages=655–668 |arxiv=2107.01391 }}</ref>
 ==== Quicksort ====

Kvng: /* Bubble sort */ rm stray irrelevant ref

2025-04-12T14:37:21Z

Bubble sort: rm stray irrelevant ref

← Previous revision		Revision as of 14:37, 12 April 2025
Line 687:		Line 687:

	''Bubble sort'' is a simple sorting algorithm. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.<ref>{{harvnb\|Wirth\|1986\|pp=81–82}}</ref> This algorithm's average time and worst-case performance is O(''n''<sup>2</sup>), so it is rarely used to sort large, unordered data sets. Bubble sort can be used to sort a small number of items (where its asymptotic inefficiency is not a high penalty). Bubble sort can also be used efficiently on a list of any length that is nearly sorted (that is, the elements are not significantly out of place). For example, if any number of elements are out of place by only one position (e.g. 0123546789 and 1032547698), bubble sort's exchange will get them in order on the first pass, the second pass will find all elements in order, so the sort will take only 2''n'' time.		''Bubble sort'' is a simple sorting algorithm. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.<ref>{{harvnb\|Wirth\|1986\|pp=81–82}}</ref> This algorithm's average time and worst-case performance is O(''n''<sup>2</sup>), so it is rarely used to sort large, unordered data sets. Bubble sort can be used to sort a small number of items (where its asymptotic inefficiency is not a high penalty). Bubble sort can also be used efficiently on a list of any length that is nearly sorted (that is, the elements are not significantly out of place). For example, if any number of elements are out of place by only one position (e.g. 0123546789 and 1032547698), bubble sort's exchange will get them in order on the first pass, the second pass will find all elements in order, so the sort will take only 2''n'' time.

	<ref>{{Cite web
	\| url=https://github.com/torvalds/linux/blob/72932611b4b05bbd89fafa369d564ac8e449809b/kernel/groups.c#L105
	\| title=kernel/groups.c
	\| website=[[GitHub]]
	\| access-date=2012-05-05
	\| archive-date=2021-02-25
	\| archive-url=https://web.archive.org/web/20210225154539/https://github.com/torvalds/linux/blob/72932611b4b05bbd89fafa369d564ac8e449809b/kernel/groups.c#L105
	\| url-status=live
	}}</ref>

	==== Comb sort ====		==== Comb sort ====

OAbot: Open access bot: arxiv updated in citation with #oabot.

2025-03-17T04:25:14Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 04:25, 17 March 2025
Line 646:		Line 646:

	==== Recombinant sort ====		==== Recombinant sort ====
	Recombinant sort is a novel non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm represents a synergetic combination of bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers. Unlike many traditional sorting algorithms, it maintains consistent linear performance across various input distributions.<ref>{{citation \|url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 \|title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort\|date=2020 \|doi=10.18280/isi.250513 \|last1=Kumar \|first1=Peeyush \|last2=Gangal \|first2=Ayushe \|last3=Kumari \|first3=Sunita \|journal=Ingénierie des Systèmes D Information \|volume=25 \|issue=5 \|pages=655–668 }}</ref>		Recombinant sort is a novel non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm represents a synergetic combination of bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers. Unlike many traditional sorting algorithms, it maintains consistent linear performance across various input distributions.<ref>{{citation \|url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 \|title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort\|date=2020 \|doi=10.18280/isi.250513 \|last1=Kumar \|first1=Peeyush \|last2=Gangal \|first2=Ayushe \|last3=Kumari \|first3=Sunita \|journal=Ingénierie des Systèmes D Information \|volume=25 \|issue=5 \|pages=655–668 \|arxiv=2107.01391 }}</ref>

	==== Quicksort ====		==== Quicksort ====

94.175.200.195: n*k is "bad" memory-efficiency + linked exchange sort directly instead of section in this article

2025-03-13T19:19:48Z

n*k is "bad" memory-efficiency + linked exchange sort directly instead of section in this article

← Previous revision		Revision as of 19:19, 13 March 2025
Line 328:		Line 328:

	\|- align="center"		\|- align="center"
	\| [[~~#Exchange_sort\|~~Exchange sort]]		\| [[Exchange sort]]
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
Line 354:		Line 354:
	\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}		\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}
	\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}		\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}
	\| style="background:#~~dfd~~" \| {{Sort\|10\|<math>n k</math>}}		\| style="background:#fdd" \| {{Sort\|10\|<math>n k</math>}}
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No

Citation bot: Add: pages, issue, volume, journal, doi, date, authors 1-3. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Jim.belk/Most_viewed_math_articles_(2010) | #UCB_webform_linked 854/998

2025-03-12T17:39:15Z

Add: pages, issue, volume, journal, doi, date, authors 1-3. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Jim.belk/Most_viewed_math_articles_(2010) | #UCB_webform_linked 854/998

← Previous revision		Revision as of 17:39, 12 March 2025
Line 646:		Line 646:

	==== Recombinant sort ====		==== Recombinant sort ====
	Recombinant sort is a novel non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm represents a synergetic combination of bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers. Unlike many traditional sorting algorithms, it maintains consistent linear performance across various input distributions.<ref>{{citation \|url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 \|title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort}}</ref>		Recombinant sort is a novel non-comparison-based sorting algorithm developed by Peeyush Kumar et al in 2020. The algorithm represents a synergetic combination of bucket sort, counting sort, radix sort, hashing, and dynamic programming techniques. It employs an n-dimensional Cartesian space mapping approach consisting of two primary phases: a Hashing cycle that maps elements to a multidimensional array using a special hash function, and an Extraction cycle that retrieves elements in sorted order. Recombinant Sort achieves O(n) time complexity for best, average, and worst cases, and can process both numerical and string data types, including mixed decimal and non-decimal numbers. Unlike many traditional sorting algorithms, it maintains consistent linear performance across various input distributions.<ref>{{citation \|url=https://www.iieta.org/journals/isi/paper/10.18280/isi.250513 \|title=Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort\|date=2020 \|doi=10.18280/isi.250513 \|last1=Kumar \|first1=Peeyush \|last2=Gangal \|first2=Ayushe \|last3=Kumari \|first3=Sunita \|journal=Ingénierie des Systèmes D Information \|volume=25 \|issue=5 \|pages=655–668 }}</ref>

	==== Quicksort ====		==== Quicksort ====

DPenner1: /* Comparison sorts */ Surely it makes more sense to shade the $n \log n$ values yellow in the Best case column since $n$ is the optimal value

2025-03-12T13:44:51Z

Comparison sorts: Surely it makes more sense to shade the <math>n \log n</math> values yellow in the Best case column since <math>n</math> is the optimal value

← Previous revision		Revision as of 13:44, 12 March 2025
Line 95:		Line 95:
	\|- align="center"		\|- align="center"
	\| [[Heapsort]]		\| [[Heapsort]]
	\|style="background:#~~dfd~~"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#ffd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
Line 105:		Line 105:
	\|- align="center"		\|- align="center"
	\| [[Introsort]]		\| [[Introsort]]
	\|style="background:#~~dfd~~"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#ffd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
Line 115:		Line 115:
	\|- align="center"		\|- align="center"
	\| [[Merge sort]]		\| [[Merge sort]]
	\|style="background:#~~dfd~~"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#ffd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
Line 125:		Line 125:
	\|- align="center"		\|- align="center"
	\| [[Tournament sort]]		\| [[Tournament sort]]
	\| style="background:#~~dfd~~" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
Line 135:		Line 135:
	\|- align="center"		\|- align="center"
	\| [[Tree sort]]		\| [[Tree sort]]
	\| style="background:#~~dfd~~" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math><wbr/>(balanced)}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math><wbr/>(balanced)}}
Line 197:		Line 197:
	\|- align="center"		\|- align="center"
	\| [[Quicksort]]		\| [[Quicksort]]
	\|style="background:#~~dfd~~"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#ffd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}		\|style="background:#dfd"\| {{Sort\|20\|<math>n \log n</math>}}
	\|style="background:#fdd"\| {{Sort\|25\|<math>n^2</math>}}		\|style="background:#fdd"\| {{Sort\|25\|<math>n^2</math>}}
Line 208:		Line 208:
	\|- align="center"		\|- align="center"
	\| [[Library sort]]		\| [[Library sort]]
	\| style="background:#~~dfd~~" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
Line 219:		Line 219:
	\|- align="center"		\|- align="center"
	\| [[Shellsort]]		\| [[Shellsort]]
	\| style="background:#~~dfd~~" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#ffd" \| {{Sort\|23\|<math>n^{4/3}</math>}}		\| style="background:#ffd" \| {{Sort\|23\|<math>n^{4/3}</math>}}
	\| style="background:#ffd" \| {{Sort\|23\|<math>n^{3/2}</math>}}		\| style="background:#ffd" \| {{Sort\|23\|<math>n^{3/2}</math>}}
Line 230:		Line 230:
	\|- align="center"		\|- align="center"
	\| [[Comb sort]]		\| [[Comb sort]]
	\| style="background:#~~dfd~~" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}

AnomieBOT: Dating maintenance tags: {{Who}}

2025-03-09T21:30:23Z

Dating maintenance tags: {{Who}}

← Previous revision		Revision as of 21:30, 9 March 2025
Line 608:		Line 608:
	* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>		* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>
	* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>		* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>
	* One of the authors of the previously mentioned algorithm{{who}} also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.<!--modification seems strictly worse?-->		* One of the authors of the previously mentioned algorithm{{who\|date=March 2025}} also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.<!--modification seems strictly worse?-->

	== Popular sorting algorithms ==		== Popular sorting algorithms ==

94.175.200.195: /* Others */{{who}} + comment (how is modification of algorithm useful?)

2025-03-09T19:30:05Z

Others: {{who}} + comment (how is modification of algorithm useful?)

← Previous revision		Revision as of 19:30, 9 March 2025
Line 608:		Line 608:
	* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>		* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>
	* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>		* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>
	* One of the authors of the previously mentioned algorithm also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.		* One of the authors of the previously mentioned algorithm{{who}} also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.<!--modification seems strictly worse?-->

	== Popular sorting algorithms ==		== Popular sorting algorithms ==

94.175.200.195: /* Others */i think that’s what it means?

2025-03-09T19:19:17Z

Others: i think that’s what it means?

← Previous revision		Revision as of 19:19, 9 March 2025
Line 608:		Line 608:
	* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>		* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math\|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal \|doi=10.1006/jagm.2002.1211 \|title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations \|journal=Journal of Algorithms \|volume=42 \|issue=2 \|pages=205–230 \|date=February 2002 \|last1=Thorup \|first1=M. \|s2cid=9700543 \|author1-link = Mikkel Thorup}}</ref>
	* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>		* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference \|doi=10.1109/SFCS.2002.1181890 \|title=Integer sorting in O(n√(log log n)) expected time and linear space \|conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] \|pages=135–144 \|year=2002 \|first1=Yijie \|last1=Han \|last2=Thorup \|first2=M. \|author2-link = Mikkel Thorup \|isbn=0-7695-1822-2}}</ref>
	* One of the authors of the previously mentioned algorithm also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers.<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> ~~Further~~ ~~claiming~~ that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.		* One of the authors of the previously mentioned algorithm also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal \|last=Han \|first=Yijie \|date=2020-04-01 \|title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space \|url=https://doi.org/10.1007/s00453-019-00626-0 \|journal=Algorithmica \|language=en \|volume=82 \|issue=4 \|pages=966–978 \|doi=10.1007/s00453-019-00626-0 \|issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.

	== Popular sorting algorithms ==		== Popular sorting algorithms ==

94.175.200.195: /* Others */Added {{section link}} template

2025-03-09T19:08:36Z

Others: Added {{section link}} template

← Previous revision		Revision as of 19:08, 9 March 2025
Line 526:		Line 526:
	\| {{Yes}}		\| {{Yes}}
	\| Polling		\| Polling
	\|align="left"\| This is a linear-time, analog algorithm for sorting a sequence of items, requiring ''O''(''n'') stack space, and the sort is stable. This requires ''n'' parallel processors. See [[spaghetti sort#Analysis]].<!-- see talk page discussion for June 2011 -->		\|align="left"\| This is a linear-time, analog algorithm for sorting a sequence of items, requiring ''O''(''n'') stack space, and the sort is stable. This requires ''n'' parallel processors. See {{section link\|spaghetti sort#Analysis}}.<!-- see talk page discussion for June 2011 -->
	\|- align="center"		\|- align="center"
	\| [[Sorting network]]		\| [[Sorting network]]

← Previous revision		Revision as of 19:19, 13 March 2025
Line 328:		Line 328:

	\|- align="center"		\|- align="center"
	\| [[~~#Exchange_sort\|~~Exchange sort]]		\| [[Exchange sort]]
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
	\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}		\| style="background:#fdd" \| {{Sort\|25\|<math>n^2</math>}}
Line 354:		Line 354:
	\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}		\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}
	\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}		\| style="background:#dfd" \| {{Sort\|25\|<math>n</math>}}
	\| style="background:#~~dfd~~" \| {{Sort\|10\|<math>n k</math>}}		\| style="background:#fdd" \| {{Sort\|10\|<math>n k</math>}}
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No