Editing Sorting algorithm (section)

== Popular sorting algorithms ==
While there are a large number of sorting algorithms, in practical implementations a few algorithms predominate. Insertion sort is widely used for small data sets, while for large data sets an asymptotically efficient sort is used, primarily heapsort, merge sort, or quicksort. Efficient implementations generally use a [[hybrid algorithm]], combining an asymptotically efficient algorithm for the overall sort with insertion sort for small lists at the bottom of a recursion. Highly tuned implementations use more sophisticated variants, such as [[Timsort]] (merge sort, insertion sort, and additional logic), used in [[Android (operating system)|Android]], [[Java (programming language)|Java]], and [[Python (programming language)|Python]], and [[introsort]] (quicksort and heapsort), used (in variant forms) in some [[sort (C++)|C++ sort]] implementations and in [[.NET]].

For more restricted data, such as numbers in a fixed interval, [[#Distribution sorts|distribution sorts]] such as counting sort or radix sort are widely used. Bubble sort and variants are rarely used in practice, but are commonly found in teaching and theoretical discussions.

When physically sorting objects (such as alphabetizing papers, tests or books) people intuitively generally use insertion sorts for small sets. For larger sets, people often first bucket, such as by initial letter, and multiple bucketing allows practical sorting of very large sets. Often space is relatively cheap, such as by spreading objects out on the floor or over a large area, but operations are expensive, particularly moving an object a large distance – [[locality of reference]] is important. Merge sorts are also practical for physical objects, particularly as two hands can be used, one for each list to merge, while other algorithms, such as heapsort or quicksort, are poorly suited for human use. Other algorithms, such as [[library sort]], a variant of insertion sort that leaves spaces, are also practical for physical use.

=== Simple sorts ===
Two of the simplest sorts are insertion sort and selection sort, both of which are efficient on small data, due to low overhead, but not efficient on large data. Insertion sort is generally faster than selection sort in practice, due to fewer comparisons and good performance on almost-sorted data, and thus is preferred in practice, but selection sort uses fewer writes, and thus is used when write performance is a limiting factor.

==== Insertion sort ====
{{Main|Insertion sort}}
''[[Insertion sort]]'' is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list similar to how one puts money in their wallet.<ref>{{cite book |last=Wirth |first=Niklaus |author-link=Niklaus Wirth |title=Algorithms & Data Structures |place=Upper Saddle River, NJ |publisher=Prentice-Hall |year=1986 |isbn=978-0130220059 |pages=76–77}}</ref> In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. [[Shellsort]] is a variant of insertion sort that is more efficient for larger lists.

==== Selection sort ====
{{Main|Selection sort}}
''Selection sort'' is an [[in-place]] [[comparison sort]]. It has [[Big O notation|O]](''n''<sup>2</sup>) complexity, making it inefficient on large lists, and generally performs worse than the similar [[insertion sort]]. Selection sort is noted for its simplicity and also has performance advantages over more complicated algorithms in certain situations.

The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list.<ref>{{harvnb|Wirth|1986|pp=79–80}}</ref> It does no more than ''n'' swaps and thus is useful where swapping is very expensive.

=== Efficient sorts ===
Practical general sorting algorithms are almost always based on an algorithm with average time complexity (and generally worst-case complexity) O(''n'' log ''n''), of which the most common are heapsort, merge sort, and quicksort. Each has advantages and drawbacks, with the most significant being that simple implementation of merge sort uses O(''n'') additional space, and simple implementation of quicksort has O(''n''<sup>2</sup>) worst-case complexity. These problems can be solved or ameliorated at the cost of a more complex algorithm.

While these algorithms are asymptotically efficient on random data, for practical efficiency on real-world data various modifications are used. First, the overhead of these algorithms becomes significant on smaller data, so often a hybrid algorithm is used, commonly switching to insertion sort once the data is small enough. Second, the algorithms often perform poorly on already sorted data or almost sorted data – these are common in real-world data and can be sorted in O(''n'') time by appropriate algorithms. Finally, they may also be [[unstable sort|unstable]], and stability is often a desirable property in a sort. Thus more sophisticated algorithms are often employed, such as [[Timsort]] (based on merge sort) or [[introsort]] (based on quicksort, falling back to heapsort).

==== Merge sort ====
{{Main|Merge sort}}
''Merge sort'' takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.<ref>{{harvnb|Wirth|1986|pp=101–102}}</ref> Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(''n'' log ''n''). It is also easily applied to lists, not only arrays, as it only requires sequential access, not random access. However, it has additional O(''n'') space complexity and involves a large number of copies in simple implementations.

Merge sort has seen a relatively recent surge in popularity for practical implementations, due to its use in the sophisticated algorithm [[Timsort]], which is used for the standard sort routine in the programming languages [[Python (programming language)|Python]]<ref>{{cite web|url=http://svn.python.org/projects/python/trunk/Objects/listsort.txt|title=Tim Peters's original description of timsort|website=python.org|access-date=14 April 2018|archive-date=22 January 2018|archive-url=https://web.archive.org/web/20180122024335/http://svn.python.org/projects/python/trunk/Objects/listsort.txt|url-status=live}}</ref> and [[Java (programming language)|Java]] (as of [[JDK7]]<ref>{{cite web|url=http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java|title=OpenJDK's TimSort.java|website=java.net|access-date=14 April 2018|archive-date=14 August 2011|archive-url=https://web.archive.org/web/20110814013719/http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java|url-status=dead}}</ref>). Merge sort itself is the standard routine in [[Perl]],<ref>{{cite web|url=http://perldoc.perl.org/functions/sort.html|title=sort – perldoc.perl.org|website=perldoc.perl.org|access-date=14 April 2018|archive-date=14 April 2018|archive-url=https://web.archive.org/web/20180414233802/http://perldoc.perl.org/functions/sort.html|url-status=live}}</ref> among others, and has been used in Java at least since 2000 in [[Java version history#J2SE 1.3|JDK1.3]].<ref name="mergesort_in_jdk13">[http://java.sun.com/j2se/1.3/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) Merge sort in Java 1.3], Sun. {{Webarchive|url=https://web.archive.org/web/20090304021927/http://java.sun.com/j2se/1.3/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) |date=2009-03-04 }}</ref>

==== Heapsort ====
{{Main|Heapsort}}
''Heapsort'' is a much more efficient version of [[selection sort]]. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a [[heap (data structure)|heap]], a special type of [[binary tree]].<ref>{{harvnb|Wirth|1986|pp=87–89}}</ref> Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log ''n'') time, instead of O(''n'') for a linear scan as in simple selection sort. This allows Heapsort to run in O(''n'' log ''n'') time, and this is also the worst-case complexity.

==== Recombinant sort ====
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 ====
{{Main|Quicksort}}
''Quicksort'' is a [[divide-and-conquer algorithm]] which relies on a ''partition'' operation: to partition an array, an element called a ''pivot'' is selected.<ref>{{harvnb|Wirth|1986|p=93}}</ref><ref>{{citation |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ron Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |title=Introduction to Algorithms |edition=3rd |place=Cambridge, MA |publisher=The MIT Press |year=2009 |isbn=978-0262033848 |pages=171–172}}</ref> All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and [[in-place]]. The lesser and greater sublists are then recursively sorted. This yields an average time complexity of O(''n'' log ''n''), with low overhead, and thus this is a popular algorithm. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex but are among the fastest sorting algorithms in practice. Together with its modest O(log ''n'') space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries.

The important caveat about quicksort is that its worst-case performance is O(''n''<sup>2</sup>); while this is rare, in naive implementations (choosing the first or last element as pivot) this occurs for sorted data, which is a common case. The most complex issue in quicksort is thus choosing a good pivot element, as consistently poor choices of pivots can result in drastically slower O(''n''<sup>2</sup>) performance, but good choice of pivots yields O(''n'' log ''n'') performance, which is asymptotically optimal. For example, if at each step the [[median]] is chosen as the pivot then the algorithm works in O(''n''&nbsp;log&nbsp;''n''). Finding the median, such as by the [[median of medians]] [[selection algorithm]] is however an O(''n'') operation on unsorted lists and therefore exacts significant overhead with sorting. In practice choosing a random pivot almost certainly yields O(''n''&nbsp;log&nbsp;''n'') performance.

If a guarantee of O(''n'' log ''n'') performance is important, there is a simple modification to achieve that. The idea, due to Musser, is to set a limit on the maximum depth of recursion.<ref>{{citation |last1=Musser |first1=David R. |title=Introspective Sorting and Selection Algorithms |journal=Software: Practice and Experience |year=1997 |volume=27 |issue=8 |pages=983–993|doi=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# }}</ref> If that limit is exceeded, then sorting is continued using the heapsort algorithm. Musser proposed that the limit should be <math> 1 + 2 \lfloor \log_2(n) \rfloor</math>, which is approximately twice the maximum recursion depth one would expect on average with a randomly [[ordered array]].

==== Shellsort ====
[[File:Shell_sorting_algorithm_color_bars.svg|right|thumb|A Shellsort, different from bubble sort in that it moves elements to numerous [[Swap (computer science)|swapping positions]].]]
{{Main|Shellsort}}
''Shellsort'' was invented by [[Donald Shell]] in 1959.<ref name="Shell">{{Cite journal
  |url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |last=Shell
  |first=D. L.
  |title=A High-Speed Sorting Procedure
  |journal=Communications of the ACM
  |volume=2
  |issue=7
  |year=1959
  |pages=30–32
  |doi=10.1145/368370.368387
  |s2cid=28572656
  |access-date=2020-03-23
  |archive-date=2017-08-30
  |archive-url=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |url-status=dead
  }}</ref> It improves upon insertion sort by moving out of order elements more than one position at a time. The concept behind Shellsort is that insertion sort performs in {{tmath|O(kn)}} time, where k is the greatest distance between two out-of-place elements. This means that generally, they perform in ''O''(''n''<sup>2</sup>), but for data that is mostly sorted, with only a few elements out of place, they perform faster. So, by first sorting elements far away, and progressively shrinking the gap between the elements to sort, the final sort computes much faster. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.

The worst-case time complexity of Shellsort is an [[open problem]] and depends on the gap sequence used, with known complexities ranging from ''O''(''n''<sup>2</sup>) to ''O''(''n''<sup>4/3</sup>) and Θ(''n'' log<sup>2</sup> ''n''). This, combined with the fact that Shellsort is [[in-place]], only needs a relatively small amount of code, and does not require use of the [[call stack]], makes it is useful in situations where memory is at a premium, such as in [[embedded system]]s and [[operating system kernel]]s.

=== Bubble sort and variants ===
Bubble sort, and variants such as the [[Comb sort]] and [[cocktail sort]], are simple, highly inefficient sorting algorithms. They are frequently seen in introductory texts due to ease of analysis, but they are rarely used in practice.

==== Bubble sort ====
[[File:Bubblesort-edited-color.svg|thumb|right|A bubble sort, a sorting algorithm that continuously steps through a list, [[Swap (computer science)|swapping]] items until they appear in the correct order.]]
{{Main|Bubble sort}}

''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.

==== Comb sort ====
{{Main|Comb sort}}
''Comb sort'' is a relatively simple sorting algorithm based on [[bubble sort]] and originally designed by Włodzimierz Dobosiewicz in 1980.<ref name=BB>{{Cite journal | doi = 10.1016/S0020-0190(00)00223-4| title = Analyzing variants of Shellsort| journal = [[Inf. Process. Lett.]]| volume = 79| issue = 5| pages = 223–227
| date = 15 September 2001| last1 = Brejová | first1 = B. }}</ref> It was later rediscovered and popularized by Stephen Lacey and Richard Box with a [[Byte Magazine|''Byte'' Magazine]] article published in April 1991. The basic idea is to eliminate ''turtles'', or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (''Rabbits'', large values around the beginning of the list, do not pose a problem in bubble sort) It accomplishes this by initially swapping elements that are a certain distance from one another in the array, rather than only swapping elements if they are adjacent to one another, and then shrinking the chosen distance until it is operating as a normal bubble sort. Thus, if Shellsort can be thought of as a generalized version of insertion sort that swaps elements spaced a certain distance away from one another, comb sort can be thought of as the same generalization applied to bubble sort.

==== Exchange sort ====
''Exchange sort'' is sometimes confused with bubble sort, although the algorithms are in fact distinct.<ref>{{Cite web|url=https://www.codingunit.com/exchange-sort-algorithm|title=Exchange Sort Algorithm|website=CodingUnit Programming Tutorials|access-date=2021-07-10|archive-date=2021-07-10|archive-url=https://web.archive.org/web/20210710111758/https://www.codingunit.com/exchange-sort-algorithm|url-status=live}}</ref><ref>{{Cite web|url=https://mathbits.com/MathBits/Java/arrays/Exchange.htm|title=Exchange Sort|website=JavaBitsNotebook.com|access-date=2021-07-10|archive-date=2021-07-10|archive-url=https://web.archive.org/web/20210710111757/https://mathbits.com/MathBits/Java/arrays/Exchange.htm|url-status=live}}</ref> Exchange sort works by comparing the first element with all elements above it, swapping where needed, thereby guaranteeing that the first element is correct for the final sort order; it then proceeds to do the same for the second element, and so on. It lacks the advantage that bubble sort has of detecting in one pass if the list is already sorted, but it can be faster than bubble sort by a constant factor (one less pass over the data to be sorted; half as many total comparisons) in worst-case situations. Like any simple O(''n''<sup>2</sup>) sort it can be reasonably fast over very small data sets, though in general [[insertion sort]] will be faster.

=== Distribution sorts ===
{{see also|External sorting}}
''Distribution sort'' refers to any sorting algorithm where data is distributed from their input to multiple intermediate structures which are then gathered and placed on the output. For example, both [[bucket sort]] and [[flashsort]] are distribution-based sorting algorithms. Distribution sorting algorithms can be used on a single processor, or they can be a [[distributed algorithm]], where individual subsets are separately sorted on different processors, then combined. This allows [[external sorting]] of data too large to fit into a single computer's memory.

==== Counting sort ====
{{Main|Counting sort}}
Counting sort is applicable when each input is known to belong to a particular set, ''S'', of possibilities.  The algorithm runs in O(|''S''| + ''n'') time and O(|''S''|) memory where ''n'' is the length of the input.  It works by creating an integer array of size |''S''| and using the ''i''th bin to count the occurrences of the ''i''th member of ''S'' in the input.  Each input is then counted by incrementing the value of its corresponding bin.  Afterward, the counting array is looped through to arrange all of the inputs in order.  This sorting algorithm often cannot be used because ''S'' needs to be reasonably small for the algorithm to be efficient, but it is extremely fast and demonstrates great asymptotic behavior as ''n'' increases.  It also can be modified to provide stable behavior.

==== Bucket sort ====
{{Main|Bucket sort}}
Bucket sort is a [[divide-and-conquer algorithm|divide-and-conquer]] sorting algorithm that generalizes [[counting sort]] by partitioning an array into a finite number of buckets.  Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sorting algorithm.

A bucket sort works best when the elements of the data set are evenly distributed across all buckets.

==== Radix sort ====
{{Main|Radix sort}}
''Radix sort'' is an algorithm that sorts numbers by processing individual digits. ''n'' numbers consisting of ''k'' digits each are sorted in O(''n'' · ''k'') time.  Radix sort can process digits of each number either starting from the [[least significant digit]] (LSD) or starting from the [[most significant digit]] (MSD).  The LSD algorithm first sorts the list by the least significant digit while preserving their relative order using a stable sort. Then it sorts them by the next digit, and so on from the least significant to the most significant, ending up with a sorted list. While the LSD radix sort requires the use of a stable sort, the MSD radix sort algorithm does not (unless stable sorting is desired).  In-place MSD radix sort is not stable.  It is common for the [[counting sort]] algorithm to be used internally by the radix sort.  A [[hybrid algorithm|hybrid]] sorting approach, such as using [[insertion sort]] for small bins, improves performance of radix sort significantly.