Sorting algorithm - Revision history

imported>Crow Basket: Reverted 1 edit by ~2025-42827-95 (talk) to last revision by CodeTalker

2025-12-24T16:58:39Z

Reverted 1 edit by ~2025-42827-95 (talk) to last revision by CodeTalker

← Previous revision		Revision as of 16:58, 24 December 2025
Line 37:		Line 37:
	[[File:Sorting stability playing cards.svg\|thumb\|An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output.]]		[[File:Sorting stability playing cards.svg\|thumb\|An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output.]]

	Stable ~~sort~~ algorithms sort equal elements in the same order that they appear in the input. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. This allows the possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal (like the two 5 cards), then their relative order will be preserved, i.e. if one comes before the other in the input, it will come before the other in the output.		'''Stable sorting algorithms''' sort equal elements in the same order that they appear in the input. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. This allows the possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal (like the two 5 cards), then their relative order will be preserved, i.e. if one comes before the other in the input, it will come before the other in the output.

	Stability is important to preserve order over multiple sorts on the same [[data set]]. For example, say that student records consisting of name and class section are sorted dynamically, first by name, then by class section. If a stable sorting algorithm is used in both cases, the sort-by-class-section operation will not change the name order; with an unstable sort, it could be that sorting by section shuffles the name order, resulting in a nonalphabetical list of students.		Stability is important to preserve order over multiple sorts on the same [[data set]]. For example, say that student records consisting of name and class section are sorted dynamically, first by name, then by class section. If a stable sorting algorithm is used in both cases, the sort-by-class-section operation will not change the name order; with an unstable sort, it could be that sorting by section shuffles the name order, resulting in a nonalphabetical list of students.
Line 416:		Line 416:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Least significant digit\|LSD Radix Sort]]		\| [[Radix sort#Least significant digit\|LSD Radix Sort]]
	\|style="background:#dfd"\| <math>n</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
Line 426:		Line 426:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]]		\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]]
	\| —		\|style="background:#dfd"\| <math>n</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
Line 436:		Line 436:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]] (in-place)		\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]] (in-place)
	\| —		\|style="background:#dfd"\| <math>n</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>
Line 592:		Line 592:
	\| {{No}}		\| {{No}}
	\|align="left"\| Parody sorting algorithm to show the risk of overly relying on Big O notation - runs a merge sort and then sleeps until a fixed constant amount of time has elapsed from the function call, thus (wastefully) guaranteeing a fixed runtime below the hardcoded minimum.		\|align="left"\| Parody sorting algorithm to show the risk of overly relying on Big O notation - runs a merge sort and then sleeps until a fixed constant amount of time has elapsed from the function call, thus (wastefully) guaranteeing a fixed runtime below the hardcoded minimum.
	~~\|- align="center"~~
	\|- align="center"		\|- align="center"
	\| [[Stooge sort]]		\| [[Stooge sort]]
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|15\|{{mvar\|n}}}}		\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}
	\| {{No}}		\| {{No}}
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math\|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].		\| align="left" \| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math\|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].
	\|- align="center"		\|- align="center"
	\| [[Slowsort]]		\| [[Slowsort]]
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|15\|{{mvar\|n}}}}		\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}
	\| {{No}}		\| {{No}}
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].		\| align="left" \| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].
	\|- align="center"		\|- align="center"
	\| Franceschini's method<ref>{{Cite journal \| doi = 10.1007/s00224-006-1311-1\| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves\| journal = Theory of Computing Systems\| volume = 40\| issue = 4\| pages = 327–353		\| Franceschini's method<ref>{{Cite journal \| doi = 10.1007/s00224-006-1311-1\| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves\| journal = Theory of Computing Systems\| volume = 40\| issue = 4\| pages = 327–353
	\| date = June 2007\| last1 = Franceschini \| first1 = G. }}</ref>		\| date = June 2007\| last1 = Franceschini \| first1 = G. }}</ref>
	\|{{Sort\|20\|<math>-</math>}}		\|{{Sort\|20\|<math>-</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>}}
			\| style="background:#dfd" \| {{Sort\|00\|1}}
			\| {{Yes}} <!--Franceschini's 2007 sort IS STABLE. Not to be confused with Franceschini's 2003 sort which is NOT STABLE-->
			\| {{Yes}}
			\| align="left" \| Makes {{math\|''O''(''n'')}} data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
			\|- align="center"
			\|Heat Death Sort<ref>{{Cite web \|last=Jweda \|first=Leo \|date=2025-04-01 \|title=Constant-Time Comparison Sorting Algorithm - Leo Jweda \|url=https://www.leojweda.com/blog/constant-time-comparison-sorting-algorithm-80/ \|access-date=2025-11-25 \|language=en-CA}}</ref>
			\|style="background:#dfd"\| {{Sort\|00\|1}}
			\|style="background:#dfd"\| {{Sort\|00\|1}}
	\|style="background:#dfd"\| {{Sort\|00\|1}}		\|style="background:#dfd"\| {{Sort\|00\|1}}
	\| {{~~Yes~~}} ~~<!--Franceschini's 2007 sort IS STABLE. Not to be confused with Franceschini's 2003 sort which is NOT STABLE-->~~		\| {{Varies}} (depends on the underlying sorting algorithm)
			\| {{Varies}} (depends on the underlying sorting algorithm)
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| ~~Makes {{math\|~~'~~'O''(''n'')}} data moves in~~ the ~~worst case. Possesses ideal comparison sort asymptotic bounds but is only~~ of ~~theoretical interest~~.		\| align="left" \|Created as an April Fools' joke to highlight the weakness of ignoring the size of the constant in Big O notation.
	\|}		\|}
	Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:		Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:

imported>BunnysBot: Fix CW Errors with GenFixes (T1)

2025-11-18T07:25:07Z

Fix CW Errors with GenFixes (T1)

Show changes

imported>Jingjingzhang773: Added more details on Tournament Sort.

2025-06-28T12:24:55Z

Added more details on Tournament Sort.

← Previous revision		Revision as of 12:24, 28 June 2025
Line 91:		Line 91:
	\|style="background:#dfd"\| Yes		\|style="background:#dfd"\| Yes
	\| Selection		\| Selection
	\|align="left"\| ~~Constructs~~ and ~~maintains~~ a max heap to find the maximum in <math>O(\log n)</math> time ~~to perform selection sort~~.		\|align="left"\| An optimized version of selection sort. Performs selection sort by constructing and maintaining a max heap to find the maximum in <math>O(\log n)</math> time.
	\|- align="center"		\|- align="center"
	\| [[Introsort]]		\| [[Introsort]]
Line 122:		Line 122:
	\| style="background:#dfd" \| Yes		\| style="background:#dfd" \| Yes
	\| Merging		\| Merging
	\| align="left" \| Variation of Mergesort which uses an <math>O(n \log n)</math> in-place merge algorithm.		\| align="left" \| Variation of Mergesort which uses an <math>O(n \log n)</math> in-place merge algorithm based on Shellsort.

	\|- align="center"		\|- align="center"
Line 130:		Line 130:
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}		\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}
	\| style="background:#~~fdd~~" \| No		\| style="background:#dfd" \| Yes
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No
	\| Selection		\| Selection
	\| align="left" \| ~~Variation~~ of ~~Heapsort~~.		\| align="left" \| An optimization of Selection Sort, which uses a tournament tree to select the min/max.
	\|- align="center"		\|- align="center"
	\| [[Tree sort]]		\| [[Tree sort]]
Line 160:		Line 160:
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|00\|1}}		\| style="background:#dfd" \| {{Sort\|00\|1}}
	\| style="background:#~~dfd~~" \| ~~Yes~~		\| style="background:#fdd" \| No
	\| style="background:#dfd" \| Yes		\| style="background:#dfd" \| Yes
	\| Selection		\| Selection
Line 194:		Line 194:
	\| style="background:#fdd" \| No		\| style="background:#fdd" \| No
	\| Insertion		\| Insertion
	\| align="left" \| Makes ''n-1'' comparisons when the data is already sorted or reverse sorted.		\| align="left" \| Makes <math>n-1</math> comparisons when the data is already sorted or reverse sorted.

	\|- align="center"		\|- align="center"
Line 325:		Line 325:
	\| style="background:#dfd" \| Yes		\| style="background:#dfd" \| Yes
	\| Selection		\| Selection
	\| align="left" \| Noted for its simplicity.		\| align="left" \| Tiny code size. Noted for its simplicity and small number of element moves. Makes exactly <math>n</math> swaps.

	\|- align="center"		\|- align="center"
Line 356:		Line 356:
	* Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that {{math\|''n'' ≪ 2<sup>''k''</sup>}}, where ≪ means "much less than".		* Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that {{math\|''n'' ≪ 2<sup>''k''</sup>}}, where ≪ means "much less than".
	* In the unit-cost [[random-access machine]] model, algorithms with running time of <big><big><math>\scriptstyle n \cdot \frac{k}{d}</math>,</big></big> such as radix sort, still take time proportional to <small><big>{{math\|Θ(''n'' log ''n'')}}</big></small>, because {{mvar\|n}} is limited to be not more than <big><math>2^\frac{k}{d}</math>,</big> and a larger number of elements to sort would require a bigger {{mvar\|k}} in order to store them in the memory.<ref>{{cite journal \|first=Stefan \|last=Nilsson \|title=The Fastest Sorting Algorithm? \|journal=[[Dr. Dobb's]] \|year=2000 \|url=http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 \|access-date=2015-11-23 \|archive-date=2019-06-08 \|archive-url=https://web.archive.org/web/20190608084350/http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 \|url-status=live }}</ref>		* In the unit-cost [[random-access machine]] model, algorithms with running time of <big><big><math>\scriptstyle n \cdot \frac{k}{d}</math>,</big></big> such as radix sort, still take time proportional to <small><big>{{math\|Θ(''n'' log ''n'')}}</big></small>, because {{mvar\|n}} is limited to be not more than <big><math>2^\frac{k}{d}</math>,</big> and a larger number of elements to sort would require a bigger {{mvar\|k}} in order to store them in the memory.<ref>{{cite journal \|first=Stefan \|last=Nilsson \|title=The Fastest Sorting Algorithm? \|journal=[[Dr. Dobb's]] \|year=2000 \|url=http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 \|access-date=2015-11-23 \|archive-date=2019-06-08 \|archive-url=https://web.archive.org/web/20190608084350/http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 \|url-status=live }}</ref>
	*
	{\|class="wikitable sortable"		{\|class="wikitable sortable"
	\|+ Non-comparison sorts		\|+ Non-comparison sorts
Line 516:		Line 516:
	\| {{No}}		\| {{No}}
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| Notable primarily for appearing to be an erroneous implementation of either [[Insertion Sort]] or [[~~Sorting algorithm~~#Exchange sort\|Exchange Sort]].		\|align="left"\| Notable primarily for appearing to be an erroneous implementation of either [[Insertion Sort]] or [[#Exchange sort\|Exchange Sort]].
	\|- align="center"		\|- align="center"
	\| [[Spaghetti sort\|Spaghetti (Poll) sort]]		\| [[Spaghetti sort\|Spaghetti (Poll) sort]]
Line 604:		Line 604:
	\|align="left"\| Makes {{math\|''O''(''n'')}} data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.		\|align="left"\| Makes {{math\|''O''(''n'')}} data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
	\|}		\|}
	Theoretical computer scientists have ~~detailed~~ other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming ~~additional~~ constraints, including:		Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:
	* '''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>
			* AHNR algorithm,<ref>{{Cite conference
			\| last1 = Andersson
			\| first1 = Arne
			\| last2 = Hagerup
			\| first2 = Torben
			\| last3 = Nilsson
			\| first3 = Stefan
			\| last4 = Raman
			\| first4 = Rajeev
			\| title = Sorting in linear time?
			\| book-title = Proceedings of the twenty-seventh annual ACM symposium on Theory of computing
			\| editor =
			\| publisher = ACM
			\| location =
			\| pages = 427-436
			\| date =
			\| year = 1995
			\| url =
			\| doi =
			}}</ref> which runs in <math>O(n\log\log n)</math> time deterministically, and also has a randomized version which runs in linear time when words are large enough, specifically <math>w\ge (\log n)^{2+\varepsilon}</math> (where ''w'' is the word size).
	* 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\|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?-->		* 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?-->
Line 730:		Line 750:

	Sorting algorithms are ineffective for finding an order in many situations. Usually, when elements have no reliable comparison function (crowdsourced preferences like [[voting systems]]), comparisons are very costly ([[group tournament ranking system\|sports]]), or when it would be impossible to pairwise compare all elements for all criteria ([[ranking (information retrieval)\|search engines]]). In these cases, the problem is usually referred to as ''ranking'' and the goal is to find the "best" result for some criteria according to probabilities inferred from comparisons or rankings. A common example is in chess, where players are ranked with the [[Elo rating system]], and rankings are determined by a [[:Category:Tournament systems\|tournament system]] instead of a sorting algorithm.		Sorting algorithms are ineffective for finding an order in many situations. Usually, when elements have no reliable comparison function (crowdsourced preferences like [[voting systems]]), comparisons are very costly ([[group tournament ranking system\|sports]]), or when it would be impossible to pairwise compare all elements for all criteria ([[ranking (information retrieval)\|search engines]]). In these cases, the problem is usually referred to as ''ranking'' and the goal is to find the "best" result for some criteria according to probabilities inferred from comparisons or rankings. A common example is in chess, where players are ranked with the [[Elo rating system]], and rankings are determined by a [[:Category:Tournament systems\|tournament system]] instead of a sorting algorithm.

			There are sorting algorithms for a "noisy" (potentially incorrect) comparator and sorting algorithms for a pair of "fast and dirty" (i.e. "noisy") and "clean" comparators. This can be useful when the full comparison function is costly.<ref>{{Cite conference\|first1=Xingjian\|last1=Bai\|first2=Christian\|last2=Coester\|conference=NeurIPS\|year=2023\|title=Sorting with Predictions\|page=5\|url=https://proceedings.neurips.cc/paper_files/paper/2023/hash/544696ef4847c903376ed6ec58f3a703-Abstract-Conference.html}}</ref>

	== See also ==		== See also ==

imported>Joyous!: Reverted 1 edit by 212.250.19.180 (talk) to last revision by Jingjingzhang773

2025-06-10T13:21:51Z

Reverted 1 edit by 212.250.19.180 (talk) to last revision by Jingjingzhang773

← Previous revision		Revision as of 13:21, 10 June 2025
Line 114:		Line 114:

	\|- align="center"		\|- align="center"
	\| [[In-Place Merge Sort]]		\| [[Merge sort#In-place merge sort\|In-Place Merge Sort]]
	\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}
	\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}
Line 160:		Line 160:
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|00\|1}}		\| style="background:#dfd" \| {{Sort\|00\|1}}
	\| style="background:#~~fdd~~" \| No		\| style="background:#dfd" \| Yes
	\| style="background:#dfd" \| Yes		\| style="background:#dfd" \| Yes
	\| Selection		\| Selection

61.15.179.13 at 11:44, 1 June 2025

2025-06-01T11:44:45Z

Show changes

← Previous revision		Revision as of 16:58, 24 December 2025
Line 37:		Line 37:
	[[File:Sorting stability playing cards.svg\|thumb\|An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output.]]		[[File:Sorting stability playing cards.svg\|thumb\|An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output.]]

	Stable ~~sort~~ algorithms sort equal elements in the same order that they appear in the input. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. This allows the possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal (like the two 5 cards), then their relative order will be preserved, i.e. if one comes before the other in the input, it will come before the other in the output.		'''Stable sorting algorithms''' sort equal elements in the same order that they appear in the input. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. This allows the possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal (like the two 5 cards), then their relative order will be preserved, i.e. if one comes before the other in the input, it will come before the other in the output.

	Stability is important to preserve order over multiple sorts on the same [[data set]]. For example, say that student records consisting of name and class section are sorted dynamically, first by name, then by class section. If a stable sorting algorithm is used in both cases, the sort-by-class-section operation will not change the name order; with an unstable sort, it could be that sorting by section shuffles the name order, resulting in a nonalphabetical list of students.		Stability is important to preserve order over multiple sorts on the same [[data set]]. For example, say that student records consisting of name and class section are sorted dynamically, first by name, then by class section. If a stable sorting algorithm is used in both cases, the sort-by-class-section operation will not change the name order; with an unstable sort, it could be that sorting by section shuffles the name order, resulting in a nonalphabetical list of students.
Line 416:		Line 416:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Least significant digit\|LSD Radix Sort]]		\| [[Radix sort#Least significant digit\|LSD Radix Sort]]
	\|style="background:#dfd"\| <math>n</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
Line 426:		Line 426:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]]		\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]]
	\| —		\|style="background:#dfd"\| <math>n</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{d}</math>
Line 436:		Line 436:
	\|- align="center"		\|- align="center"
	\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]] (in-place)		\| [[Radix sort#Most significant digit radix sorts\|MSD Radix Sort]] (in-place)
	\| —		\|style="background:#dfd"\| <math>n</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>
	\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>		\|style="background:#dfd"\| <math>n \cdot \frac{k}{1}</math>
Line 592:		Line 592:
	\| {{No}}		\| {{No}}
	\|align="left"\| Parody sorting algorithm to show the risk of overly relying on Big O notation - runs a merge sort and then sleeps until a fixed constant amount of time has elapsed from the function call, thus (wastefully) guaranteeing a fixed runtime below the hardcoded minimum.		\|align="left"\| Parody sorting algorithm to show the risk of overly relying on Big O notation - runs a merge sort and then sleeps until a fixed constant amount of time has elapsed from the function call, thus (wastefully) guaranteeing a fixed runtime below the hardcoded minimum.
	~~\|- align="center"~~
	\|- align="center"		\|- align="center"
	\| [[Stooge sort]]		\| [[Stooge sort]]
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\log 3/\log 1.5}</math>}}
	\|style="background:#fdd"\| {{Sort\|15\|{{mvar\|n}}}}		\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}
	\| {{No}}		\| {{No}}
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math\|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].		\| align="left" \| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math\|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].
	\|- align="center"		\|- align="center"
	\| [[Slowsort]]		\| [[Slowsort]]
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}		\| style="background:#fdd" \| {{Sort\|30\|<math>n^{\Omega(\log n)}</math>}}
	\|style="background:#fdd"\| {{Sort\|15\|{{mvar\|n}}}}		\| style="background:#fdd" \| {{Sort\|15\|{{mvar\|n}}}}
	\| {{No}}		\| {{No}}
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].		\| align="left" \| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].
	\|- align="center"		\|- align="center"
	\| Franceschini's method<ref>{{Cite journal \| doi = 10.1007/s00224-006-1311-1\| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves\| journal = Theory of Computing Systems\| volume = 40\| issue = 4\| pages = 327–353		\| Franceschini's method<ref>{{Cite journal \| doi = 10.1007/s00224-006-1311-1\| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves\| journal = Theory of Computing Systems\| volume = 40\| issue = 4\| pages = 327–353
	\| date = June 2007\| last1 = Franceschini \| first1 = G. }}</ref>		\| date = June 2007\| last1 = Franceschini \| first1 = G. }}</ref>
	\|{{Sort\|20\|<math>-</math>}}		\|{{Sort\|20\|<math>-</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>}}
			\| style="background:#dfd" \| {{Sort\|00\|1}}
			\| {{Yes}} <!--Franceschini's 2007 sort IS STABLE. Not to be confused with Franceschini's 2003 sort which is NOT STABLE-->
			\| {{Yes}}
			\| align="left" \| Makes {{math\|''O''(''n'')}} data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
			\|- align="center"
			\|Heat Death Sort<ref>{{Cite web \|last=Jweda \|first=Leo \|date=2025-04-01 \|title=Constant-Time Comparison Sorting Algorithm - Leo Jweda \|url=https://www.leojweda.com/blog/constant-time-comparison-sorting-algorithm-80/ \|access-date=2025-11-25 \|language=en-CA}}</ref>
			\|style="background:#dfd"\| {{Sort\|00\|1}}
			\|style="background:#dfd"\| {{Sort\|00\|1}}
	\|style="background:#dfd"\| {{Sort\|00\|1}}		\|style="background:#dfd"\| {{Sort\|00\|1}}
	\| {{~~Yes~~}} ~~<!--Franceschini's 2007 sort IS STABLE. Not to be confused with Franceschini's 2003 sort which is NOT STABLE-->~~		\| {{Varies}} (depends on the underlying sorting algorithm)
			\| {{Varies}} (depends on the underlying sorting algorithm)
	\| {{Yes}}		\| {{Yes}}
	\|align="left"\| ~~Makes {{math\|~~'~~'O''(''n'')}} data moves in~~ the ~~worst case. Possesses ideal comparison sort asymptotic bounds but is only~~ of ~~theoretical interest~~.		\| align="left" \|Created as an April Fools' joke to highlight the weakness of ignoring the size of the constant in Big O notation.
	\|}		\|}
	Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:		Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:

← Previous revision		Revision as of 13:21, 10 June 2025
Line 114:		Line 114:

	\|- align="center"		\|- align="center"
	\| [[In-Place Merge Sort]]		\| [[Merge sort#In-place merge sort\|In-Place Merge Sort]]
	\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}
	\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}		\| style="background:#ffd" \| {{Sort\|20\|<math>n \log^2 n</math>}}
Line 160:		Line 160:
	\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}		\| style="background:#dfd" \| {{Sort\|20\|<math>n \log n</math>}}
	\| style="background:#dfd" \| {{Sort\|00\|1}}		\| style="background:#dfd" \| {{Sort\|00\|1}}
	\| style="background:#~~fdd~~" \| No		\| style="background:#dfd" \| Yes
	\| style="background:#dfd" \| Yes		\| style="background:#dfd" \| Yes
	\| Selection		\| Selection