Sorting algorithm - Knowledge

7166:, 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. 387: 7124:), 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 6959: 7388:) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort". 339: 7099: 7344:(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 7365:

RAM may become impractical. In this scenario, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at

7027:), 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. 7474:. These are fundamentally different because they require a source of random numbers. Shuffling can also be implemented by a sorting algorithm, namely by a random sort: assigning a random number to each element of the list and then sorting based on the random numbers. This is generally not done in practice, however, and there is a well-known simple and efficient algorithm for shuffling: the 355:. 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. 5002:) run time. These sorts are usually described for educational purposes to demonstrate how the run time of algorithms is estimated. The following table describes some sorting algorithms that are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements. 7178:

for the second element, and so on. It lacks the advantage which 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(

31: 6770:. 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 7395:, for example one of the ways is to combine two algorithms in a way that takes advantage of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit in RAM, the contents of each chunk sorted using an efficient algorithm (such as 7364:

When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in

7177:

is sometimes confused with bubble sort, although the algorithms are in fact distinct. 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

347:

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

6667:

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

6592:

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

228:

Sorting small arrays optimally (in fewest comparisons and swaps) or fast (i.e. taking into account machine specific details) is still an open research problem, with solutions only known for very small arrays (<20 elements). Similarly optimal (by various definitions) sorting on a parallel machine

7119:

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

6572:

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,

7380:

algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario,

6554:

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

6701:

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

6838:); 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( 369:

Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original input list as a tie-breaker.

348:

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.

342:

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

6511:

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

362:. In the card example, cards are represented as a record (rank, suit), and the key is the rank. A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list. 6892:) 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. If that limit is exceeded, then sorting is continued using the heapsort algorithm. Musser proposed that the limit should be 6827:), 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 4846:

Requires uniform distribution of elements from the domain in the array to run in linear time. If distribution is extremely skewed then it can go quadratic if underlying sort is quadratic (it is usually an insertion sort). In-place version is not stable.

130:

From the beginning of computing, the sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement. Among the authors of early sorting algorithms around 1951 was

6559:

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

6762:. 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 4977:

can be used to parallelize any of the non-comparison sorts, by efficiently distributing data into several buckets and then passing down sorting to several processors, with no need to merge as buckets are already sorted between each other.

7269:

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

7459:. Conversely, some sorting algorithms can be derived by repeated application of a selection algorithm; quicksort and quickselect can be seen as the same pivoting move, differing only in whether one recurses on both sides (quicksort, 6702:

merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(

7410:

Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with

365:

When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue. Stability is also not an issue if all keys are different.

373:

One application for stable sorting algorithms is sorting a list using a primary and secondary key. For example, suppose we wish to sort a hand of cards such that the suits are in the order clubs (♣), diamonds

6516:, 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 7813: 6492: 7300:

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.

4586: 6361: 3382: 8425: 6593:

puts money in their wallet. 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.

7497:

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

6944: 6418: 7451:

th smallest element). These can be solved inefficiently by a total sort, but more efficient algorithms exist, often derived by generalizing a sorting algorithm. The most notable example is

147:

was analyzed as early as 1956. Asymptotically optimal algorithms have been known since the mid-20th century – new algorithms are still being invented, with the widely used

396:. The same effect can be achieved with an unstable sort by using a lexicographic key comparison, which, e.g., compares first by suit, and then compares by rank if the suits are the same. 6656:), 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( 4627: 4924: 4890: 4755: 4721: 4687: 4536: 4425: 4391: 4296: 4262: 4146: 4112: 7203:

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

8671: 6117: 6072: 6027: 5936: 5886: 5836: 6668:

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(

3438: 382:), spades (♠), and within each suit, the cards are sorted by rank. This can be done by first sorting the cards by rank (using any sort), and then doing a stable sort by suit: 7591: 4214: 5778: 6983:

in 1959. 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

6551:

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.

5719: 3670: 5652: 563: 5612: 5575: 3697: 8488: 7481:

Sorting algorithms are ineffective for finding an order in many situations. Usually when elements have no reliable comparison function (crowdsourced preferences like

6229: 6197: 5271: 5237: 5203: 4958: 4330: 4180: 3561: 3527: 2192: 2139: 2101: 2063: 1978: 1946: 1828: 1796: 1737: 1705: 1624: 1592: 1526: 1494: 1422: 1390: 1293: 1261: 1193: 1161: 1129: 1074: 1042: 1010: 941: 909: 877: 796: 764: 732: 680: 648: 616: 6555:

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 –

1887: 825: 8022: 7015: 5471: 5390: 5358: 5326: 5085: 4831: 4453: 3589: 3256: 3226: 3196: 3145: 3115: 3085: 3001: 2971: 2941: 2889: 2859: 2801: 2771: 2713: 2683: 2625: 2595: 2537: 2507: 2449: 2419: 2340: 2310: 2252: 2222: 2008: 1858: 9011: 7090:, 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. 5158: 5125: 4047: 4014: 3877: 3844: 3046: 1338: 6815:

is selected. 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

6636:

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. It does no more than

4803: 4489: 3971: 3944: 3917: 3801: 3774: 3747: 3636: 319:

Whether the algorithm is serial or parallel. The remainder of this discussion almost exclusively concentrates upon serial algorithms and assumes serial operation.

8786: 7565: 6165: 4078: 392:

Within each suit, the stable sort preserves the ordering by rank that was already done. This idea can be extended to any number of keys and is utilised by

358:

More formally, the data being sorted can be represented as a record or tuple of values, and the part of the data that is used for sorting is called the

2026:

Similar to a gapped insertion sort. It requires randomly permuting the input to warrant with-high-probability time bounds, which makes it not stable.

8433: 6873:) operation on unsorted lists and therefore exacts significant overhead with sorting. In practice choosing a random pivot almost certainly yields O( 6648:

Practical general sorting algorithms are almost always based on an algorithm with average time complexity (and generally worst-case complexity) O(

404:

This analysis assumes that the length of each key is constant, and that all comparisons, swaps and other operations can proceed in constant time.

6947: 6710:). It is also easily applied to lists, not only arrays, as it only requires sequential access, not random access. However, it has additional O( 8403: 7151:

and originally designed by Włodzimierz Dobosiewicz in 1980. It was later rediscovered and popularized by Stephen Lacey and Richard Box with a

322:

Adaptability: Whether or not the presortedness of the input affects the running time. Algorithms that take this into account are known to be

9004: 8594: 8272: 7120:

first two elements, repeating until no swaps have occurred on the last pass. This algorithm's average time and worst-case performance is O(

189:

classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as

6633:. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. 8580: 6717:

Merge sort has seen a relatively recent surge in popularity for practical implementations, due to its use in the sophisticated algorithm

8661: 7948: 7274:

needs to be reasonably small for the algorithm to be efficient, but it is extremely fast and demonstrates great asymptotic behavior as

6573:

and thus is preferred in practice, but selection sort uses fewer writes, and thus is used when write performance is a limiting factor.

8228:(February 2002). "Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations". 4765:

Has better constant factor than radix sort for sorting strings. Though relies somewhat on specifics of commonly encountered strings.

8757: 7587: 7783: 3333:

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

17: 8997: 8146:

Gruber, H.; Holzer, M.; Ruepp, O. (2007), "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms",

6431: 8728: 6831:) space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries. 6428:) space, sorting real numbers. Further claiming that, without any added assumptions on the input, it can be modified to achieve 8174: 7211:

are distribution based sorting algorithms. Distribution sorting algorithms can be used on a single processor, or they can be a

8890: 8168: 8109: 7900: 7877: 7863: 7847: 7662: 4542: 8484: 6314: 8463: 8012: 6676:, and stability is often a desirable property in a sort. Thus more sophisticated algorithms are often employed, such as 3352: 178:

comparisons, where n is the number of elements in the array to be sorted). Algorithms not based on comparisons, such as

8778: 8552: 8355: 6256:

data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.

9270: 8910: 8881: 8853: 8825: 8288: 8074: 7996: 7755: 7719: 7557: 7019:

time, where k is the greatest distance between two out-of-place elements. This means that generally, they perform in

6895: 6377: 3050:

extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items.

1214: 2817:

A variant of selection sort that uses reversals, instead of just swapping the two items, after each selection scan.

8964:

A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements"

7735: 2374: 9293: 8812: 7490: 7486: 241: 8925: 9601: 4592: 1643: 7162:, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. ( 6664:) worst-case complexity. These problems can be solved or ameliorated at the cost of a more complex algorithm. 295:

Recursion: Some algorithms are either recursive or non-recursive, while others may be both (e.g., merge sort).

6722: 6529: 8125:

Fung, Stanley P. Y. (3 October 2021). "Is this the simplest (and most surprising) sorting algorithm ever?".

6374:

One of the authors of the previously mentioned algorithm also claims to have discovered an algorithm taking

9189: 9159: 9144: 7460: 7293: 6804: 6136: 5166:

is the sum of all integers to be sorted; in the case of small integers, it can be considered to be linear.

4896: 4862: 4727: 4693: 4659: 4508: 4397: 4363: 4268: 4234: 4118: 4084: 4056: 246: 214: 194: 7677:

Huang, B. C.; Langston, M. A. (December 1992). "Fast Stable Merging and Sorting in Constant Extra Space".

4968:

A variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.

4352: 4224: 9734: 9634: 7502: 6726: 6525: 6080: 6035: 5990: 5894: 5844: 5794: 288:". Strictly, an in-place sort needs only O(1) memory beyond the items being sorted; sometimes O(log 6819:. The lesser and greater sublists are then recursively sorted. This yields average time complexity of O( 9214: 9088: 9078: 9058: 8967: 8935: 8064: 6946:, which is approximately twice the maximum recursion depth one would expect on average with a randomly 6521: 9432: 8198:

Franceschini, G. (June 2007). "Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves".

7303:

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

3411: 9308: 9093: 7215:, where individual subsets are separately sorted on different processors, then combined. This allows 837: 249:

behavior in terms of the size of the list. For typical serial sorting algorithms, good behavior is O(

99:

order (each element is no smaller/larger than the previous element, according to the required order).

7830: 6738: 4192: 9739: 9606: 8395: 7692: 7475: 5745: 5740:

Random shuffling. Used for example purposes only, as even the expected best-case runtime is awful.

6629:) complexity, making it inefficient on large lists, and generally performs worse than the similar 5689: 3642: 417:

Comparison column has the following ranking classifications: "Best", "Average" and "Worst" if the

316:

Exchange sorts include bubble sort and quicksort. Selection sorts include cycle sort and heapsort.

9232: 9194: 7337: 7103: 7071: 6963: 5621: 532: 218: 8625: 7424: 6262:

Theoretical computer scientists have detailed other sorting algorithms that provide better than

5584: 5547: 1343: 309:. A comparison sort examines the data only by comparing two elements with a comparison operator. 9514: 9394: 9348: 9038: 7825: 7687: 7341: 463: 329:

Online: An algorithm such as Insertion Sort that is online can sort a constant stream of input.

222: 73: 8902: 8894: 3676: 9675: 9263: 9098: 9068: 8979: 7618: 7525: 7212: 6763: 6556: 6205: 6173: 5291:

Mostly of theoretical interest due to implementational complexity and suboptimal data moves.

5247: 5213: 5179: 5096:

Works only with positive integers. Requires specialized hardware for it to run in guaranteed

4930: 4302: 4152: 3533: 3499: 3344: 3307: 2168: 2109: 2071: 2039: 1954: 1922: 1804: 1772: 1713: 1681: 1600: 1568: 1502: 1470: 1398: 1366: 1269: 1237: 1169: 1137: 1105: 1050: 1018: 986: 917: 885: 853: 772: 740: 708: 656: 624: 592: 202: 65: 7940: 1866: 804: 84:

algorithms) that require input data to be in sorted lists. Sorting is also often useful for

9654: 9519: 9374: 9209: 9184: 9129: 8532: 8052: 7974: 7640: 7464: 6988: 5449: 5368: 5336: 5304: 5171: 5063: 4809: 4431: 3567: 3234: 3204: 3174: 3123: 3093: 3063: 2979: 2949: 2919: 2867: 2837: 2779: 2749: 2691: 2661: 2603: 2573: 2515: 2485: 2470: 2427: 2397: 2318: 2288: 2230: 2200: 1986: 1836: 959: 210: 5134: 5101: 4023: 3990: 3853: 3820: 3022: 1314: 386: 8: 9670: 9409: 9219: 9204: 9149: 8749: 8694: 8093: 7471: 7444: 7385: 7384:

One way to work around this problem, which works well when complex records (such as in a

6866: 5742:

Worst case is unbounded when using randomization, but a deterministic version guarantees

4782: 4466: 3950: 3923: 3896: 3780: 3753: 3726: 3615: 518: 284:

usage (and use of other computer resources). In particular, some sorting algorithms are "

8155:, Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197, 5495: 269:), but this is not possible in the average case. Optimal parallel sorting is O(log 9560: 9535: 9509: 9313: 9237: 9139: 9134: 9048: 8947: 8876:, The Art of Computer Programming, vol. 3 (2nd ed.), Boston: Addison-Wesley, 8617: 8245: 8126: 7922: 7772: 6564:, a variant of insertion sort that leaves spaces, are also practical for physical use. 6150: 5954:

Slower than most of the sorting algorithms (even naive ones) with a time complexity of

4063: 281: 159: 8706: 7723: 7407:. This is faster than performing either merge sort or quicksort over the entire list. 9379: 9043: 8982:– Runs a series of tests of 9 of the main sorting algorithms using Python timeit and 8906: 8877: 8849: 8821: 8720: 8548: 8351: 8325: 8284: 8164: 8105: 8070: 7992: 7873: 7843: 7751: 7658: 7520: 7498: 7489:), or when it would be impossible to pairwise compare all elements for all criteria ( 6958: 6863: 6714:) space complexity, and involves a large number of copies in simple implementations. 2646: 119: 9447: 8621: 8147: 7926: 7233:

Counting sort is applicable when each input is known to belong to a particular set,

9621: 9488: 9256: 9179: 9164: 8702: 8609: 8576: 8528: 8317: 8306:"Sorting Real Numbers in $ $ O\big (n\sqrt{\log n}\big )$ $ Time and Linear Space" 8276: 8249: 8237: 8207: 8156: 8097: 8048: 7970: 7914: 7835: 7743: 7697: 7636: 7531: 7428: 7392: 7349: 7216: 7195: 6513: 5482:

This is a linear-time, analog algorithm for sorting a sequence of items, requiring

5129:

time. There is a possibility for software implementation, but running time will be

1553: 186: 85: 77: 53: 41: 6778:) for a linear scan as in simple selection sort. This allows Heapsort to run in O( 338: 9682: 9565: 9437: 9338: 9333: 9323: 9154: 8989: 8929: 8492: 8160: 8149:

4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007

7986: 7867: 7839: 7652: 7432: 7067: 6850:) performance, which is asymptotically optimal. For example, if at each step the 6618: 6308: 5974: 5503: 3489: 3288: 3284: 2734: 1443: 978: 485: 459: 418: 306: 132: 81: 61: 7715: 7622: 7381:

another algorithm may be preferable even if it requires more total comparisons.

7062:, only needs a relatively small amount of code, and does not require use of the 9687: 9596: 9463: 9417: 9343: 9298: 9020: 8837: 8540: 8321: 8060: 7982: 7648: 7482: 7412: 7353: 7336:) time. Radix sort can process digits of each number either starting from the 7183: 6759: 6630: 6622: 6606: 6588: 6582: 6281:, a randomized algorithm for sorting keys from a domain of finite size, taking 5539: 5420: 5408: 3292: 2911: 2273: 428: 198: 190: 111: 8973: 8957: 8455: 8280: 8211: 7701: 7182:) sort it can be reasonably fast over very small data sets, though in general 6962:

A Shellsort, different from bubble sort in that it moves elements to numerous

9728: 9555: 9328: 9169: 9124: 8343: 8329: 8305: 8264: 8225: 8017: 7869:

Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4

7345: 7297: 7228: 7152: 7087: 6834:

The important caveat about quicksort is that its worst-case performance is O(

6673: 3886: 1439: 323: 179: 115: 7253:

is the length of the input. It works by creating an integer array of size |

7066:, makes it is useful in situations where memory is at a premium, such as in 5407:

Notable primarily for appearing to be an erroneous implementation of either

5289:

Makes very few comparisons worst case compared to other sorting algorithms.

424:"Memory" denotes the amount of additional storage required by the algorithm. 9570: 9483: 9353: 9119: 9083: 9053: 8983: 8960:– Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes. 8869: 8841: 8807: 8567:

Musser, David R. (1997), "Introspective Sorting and Selection Algorithms",

8241: 7537: 7366: 7102:

A bubble sort, a sorting algorithm that continuously steps through a list,

7034:

and depends on the gap sequence used, with known complexities ranging from

7031: 6980: 6721:, which is used for the standard sort routine in the programming languages 6561: 6537: 4852: 1914: 152: 91:

Formally, the output of any sorting algorithm must satisfy two conditions:

8613: 8581:

10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#

7918: 7747: 7528: – Programming idiom for efficiently sorting a list by a computed key 7098: 2553:

A variant of Bubblesort which deals well with small values at end of list

9703: 9545: 9369: 9303: 9073: 7452: 7287: 7204: 7148: 7111: 6767: 5786: 4991: 3715: 3604: 2822: 2382: 1447: 351:

Stability is important to preserve order over multiple sorts on the same

206: 144: 103: 57: 8950:– Discusses several classic algorithms and promotes alternatives to the 7740:

Proceedings of the fifteenth annual ACM symposium on Theory of computing

6597:

is a variant of insertion sort that is more efficient for larger lists.

4986:

Some algorithms are slow compared to those discussed above, such as the

370:

Remembering this order, however, may require additional time and space.

106:(a reordering, yet retaining all of the original elements) of the input. 9649: 9629: 9611: 9575: 9504: 9442: 9427: 9389: 9063: 8944:– Dictionary of algorithms, techniques, common functions, and problems. 8536: 8056: 7978: 7679: 7644: 7404: 7312: 7063: 6693: 5534:

Order of comparisons are set in advance based on a fixed network size.

4974: 4496: 3707:

Assumes uniform distribution of elements from the domain in the array.

3166: 2558: 1351: 1222: 845: 393: 34: 30: 579:

Can be implemented as a stable sort based on stable in-place merging.

302:

maintain the relative order of records with equal keys (i.e., values).

9644: 9580: 9550: 9540: 9478: 9473: 9468: 9399: 9384: 9248: 9024: 8951: 7905: 7514: 7456: 7396: 7377: 7208: 7139: 7083: 6971: 6795: 6681: 6594: 6533: 5034: 4770: 4649: 2160: 2031: 1764: 1097: 700: 96: 49: 8692:

Brejová, B. (15 September 2001). "Analyzing variants of Shellsort".

7320:

is an algorithm that sorts numbers by processing individual digits.

9713: 9708: 9422: 8131: 7373:

speed), which, compared to disk speed, is virtually instantaneous.

7059: 6816: 6750: 6615: 5982: 5674: 4987: 1666: 584: 352: 285: 8269:

Integer sorting in O(n√(log log n)) expected time and linear space

7391:

Another technique for overcoming the memory-size problem is using

7356:

for small bins, improves performance of radix sort significantly.

9639: 9174: 6737:, among others, and has been used in Java at least since 2000 in 6718: 6677: 6660:) additional space, and simple implementation of quicksort has O( 6517: 1455: 148: 69: 8547:(3rd ed.), Cambridge, MA: The MIT Press, pp. 171–172, 7278:

increases. It also can be modified to provide stable behavior.

7158:

article published in April 1991. The basic idea is to eliminate

158:

Comparison sorting algorithms have a fundamental requirement of

8976:– Visualization of Sorting Algorithms on Many Famous Paintings. 8666: 6851: 6547:

For more restricted data, such as numbers in a fixed interval,

3442:

and a larger number of elements to sort would require a bigger

1759:

comparisons when the data is already sorted or reverse sorted.

1548:

comparisons when the data is already sorted or reverse sorted.

140: 8102:

Algorithm Design: Foundations, Analysis, and Internet Examples

6274:) time complexity assuming additional constraints, including: 8941: 7941:"SELECTION SORT (Java, C++) – Algorithms and Data Structures" 7517: – Assembly of written information into a standard order 170:

comparisons (some input sequences will require a multiple of

136: 110:

For optimum efficiency, the input data should be stored in a

6672:) time by appropriate algorithms. Finally, they may also be 6640:

swaps, and thus is useful where swapping is very expensive.

6520:(merge sort, insertion sort, and additional logic), used in 4218:

Unlike most distribution sorts, this can sort non-integers.

427:

The run times and the memory requirements listed are inside

9103: 8963: 7991:(2nd ed.), Cambridge, MA: The MIT Press, p. 165, 7821: 7657:(3rd ed.), Cambridge, MA: The MIT Press, p. 167, 6734: 6730: 6541: 6487:{\displaystyle O\left(n\log n/{\sqrt {\log \log n}}\right)} 8527: 8047: 7969: 7635: 7359: 7219:

of data too large to fit into a single computer's memory.

6536:(quicksort and heapsort), used (in variant forms) in some 5528:

Varies (stable sorting networks require more comparisons)

466:

demonstrates a comparison sort cannot perform better than

8350:. Upper Saddle River, NJ: Prentice-Hall. pp. 76–77. 7558:"Meet the 'Refrigerator Ladies' Who Programmed the ENIAC" 7493:). In these cases, the problem is usually referred to as 7370: 312:

General method: insertion, exchange, selection, merging,

8942:

Dictionary of Algorithms, Data Structures, and Problems

8938:– Explanations and analyses of many sorting algorithms. 7348:

algorithm to be used internally by the radix sort. A

6811:

operation: to partition an array, an element called a

4581:{\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)} 3356: 3272:

In-place with theoretically optimal number of writes.

8974:

Sorting Algorithms Used on Famous Paintings (Youtube)

7588:"Frances E. Holberton, 84, Early Computer Programmer" 7534: – Any algorithm which solves the search problem 6991: 6898: 6854:

is chosen as the pivot then the algorithm works in O(

6434: 6380: 6317: 6208: 6176: 6153: 6083: 6038: 5993: 5897: 5847: 5797: 5748: 5692: 5624: 5587: 5550: 5490:) stack space, and the sort is stable. This requires 5452: 5371: 5339: 5307: 5250: 5216: 5182: 5137: 5104: 5066: 4933: 4899: 4865: 4812: 4785: 4730: 4696: 4662: 4595: 4545: 4511: 4469: 4434: 4400: 4366: 4305: 4271: 4237: 4195: 4155: 4121: 4087: 4066: 4026: 3993: 3953: 3926: 3899: 3856: 3823: 3783: 3756: 3729: 3679: 3645: 3618: 3570: 3536: 3502: 3414: 3355: 3287:

algorithms and other sorting algorithms that are not

3237: 3207: 3177: 3126: 3096: 3066: 3025: 2982: 2952: 2922: 2870: 2840: 2782: 2752: 2694: 2664: 2606: 2576: 2518: 2488: 2430: 2400: 2321: 2291: 2233: 2203: 2171: 2112: 2074: 2042: 1989: 1957: 1925: 1869: 1839: 1807: 1775: 1716: 1684: 1603: 1571: 1505: 1473: 1401: 1369: 1317: 1272: 1240: 1172: 1140: 1108: 1053: 1021: 989: 920: 888: 856: 807: 775: 743: 711: 659: 627: 595: 535: 7714: 6786:) time, and this is also the worst case complexity. 6356:{\displaystyle O\left(n{\sqrt {\log \log n}}\right)} 6135:

A multiply and surrender algorithm, antonymous with

3387:

such as radix sort, still take time proportional to

8779:"tag sort Definition from PC Magazine Encyclopedia" 7893: 7415:, i.e., to reduce the amount of swapping required. 4346:Same as the LSD variant, it can sort non-integers. 431:, hence the base of the logarithms does not matter. 9019: 8478: 7147:is a relatively simple sorting algorithm based on 7058:). This, combined with the fact that Shellsort is 7030:The worst-case time complexity of Shellsort is an 7009: 6938: 6842:) performance, but good choice of pivots yields O( 6486: 6412: 6355: 6223: 6191: 6159: 6111: 6066: 6021: 5930: 5880: 5830: 5772: 5713: 5646: 5606: 5569: 5465: 5384: 5352: 5320: 5265: 5231: 5197: 5152: 5119: 5079: 4952: 4918: 4884: 4825: 4797: 4749: 4715: 4681: 4621: 4580: 4530: 4483: 4447: 4419: 4385: 4324: 4290: 4256: 4208: 4174: 4140: 4106: 4072: 4041: 4008: 3965: 3938: 3911: 3871: 3838: 3795: 3768: 3741: 3691: 3664: 3630: 3583: 3555: 3521: 3432: 3377:{\displaystyle \scriptstyle n\cdot {\frac {k}{d}}} 3376: 3250: 3220: 3190: 3139: 3109: 3079: 3040: 2995: 2965: 2935: 2883: 2853: 2795: 2765: 2707: 2677: 2619: 2589: 2531: 2501: 2443: 2413: 2334: 2304: 2246: 2216: 2186: 2133: 2095: 2057: 2002: 1972: 1940: 1881: 1852: 1822: 1790: 1731: 1699: 1618: 1586: 1520: 1488: 1416: 1384: 1332: 1287: 1255: 1187: 1155: 1123: 1068: 1036: 1004: 935: 903: 871: 819: 790: 758: 726: 674: 642: 610: 557: 8145: 185:Sorting algorithms are prevalent in introductory 9726: 8895:"Efficient Sorting by Computer: An Introduction" 8092: 7818:Theory and Applications of Models of Computation 7540: – Sorting algorithms for quantum computers 6733:). Merge sort itself is the standard routine in 6684:(based on quicksort, falling back to heapsort). 68:, and either ascending or descending. Efficient 7470:A kind of opposite of a sorting algorithm is a 6939:{\displaystyle 1+2\lfloor \log _{2}(n)\rfloor } 6413:{\displaystyle O\left(n{\sqrt {\log n}}\right)} 8396:"Tim Peters's original description of timsort" 7237:, of possibilities. The algorithm runs in O(| 4340:Stable version uses an external array of size 88:data and for producing human-readable output. 9264: 9005: 8948:Slightly Skeptical View on Sorting Algorithms 8828:, Section 5.4: External Sorting, pp. 248–379. 7676: 7106:items until they appear in the correct order. 6506: 5669:An effective variation of Sorting networks. 2370:, in the worst case over sequences that have 292:) additional memory is considered "in-place". 8958:15 Sorting Algorithms in 6 Minutes (Youtube) 8273:Symposium on Foundations of Computer Science 8197: 7439:smallest elements of a list, or finding the 6933: 6908: 4637:Asymptotic are based on the assumption that 8104:. John Wiley & Sons. pp. 241–243. 8069:(2nd ed.). MIT Press and McGraw-Hill. 7903:(1978). "Implementing Quicksort programs". 7550: 7077: 6234: 6202: 6170: 6147: 6122: 6077: 6032: 5987: 5941: 5891: 5841: 5791: 5729: 5724: 5686: 5679: 5658: 5618: 5581: 5544: 5523: 5518: 5513: 5508: 5446: 5439: 5432: 5425: 5396: 5364: 5332: 5300: 5278: 5244: 5210: 5176: 5060: 5053: 5046: 5039: 4644:, but the algorithm does not require this. 3261: 3231: 3201: 3171: 3150: 3120: 3090: 3060: 3006: 2976: 2946: 2916: 2894: 2864: 2834: 2827: 2806: 2776: 2746: 2739: 2718: 2688: 2658: 2651: 2630: 2600: 2570: 2563: 2542: 2512: 2482: 2475: 2454: 2424: 2394: 2387: 2345: 2315: 2285: 2278: 2257: 2227: 2197: 2165: 2144: 2106: 2068: 2036: 2013: 1983: 1951: 1919: 1863: 1833: 1801: 1769: 1742: 1710: 1678: 1671: 1629: 1597: 1565: 1558: 1531: 1499: 1467: 1460: 1427: 1395: 1363: 1356: 1298: 1266: 1234: 1227: 1200: 1166: 1134: 1102: 1079: 1047: 1015: 983: 946: 914: 882: 850: 801: 769: 737: 705: 685: 653: 621: 589: 568: 529: 399: 9271: 9257: 9012: 8998: 8936:Sequential and parallel sorting algorithms 8100:(2002). "4.5 Bucket-Sort and Radix-Sort". 7807: 2729:Can be run on parallel processors easily. 8262: 8130: 7899: 7862: 7829: 7770: 7691: 4622:{\displaystyle {\frac {k}{d}}\cdot 2^{d}} 265:). Ideal behavior for a serial sort is O( 237:Sorting algorithms can be classified by: 8820:, Second Edition. Addison-Wesley, 1998, 7427:(sorting a sequence to within a certain 7097: 6957: 1898:Quicksort is usually done in-place with 973:using the Three Hungarians' Algorithm). 337: 29: 8691: 8043: 8041: 8039: 8010: 7360:Memory usage patterns and index sorting 7261:th bin to count the occurrences of the 6548: 3347:model, algorithms with running time of 3278: 125: 14: 9727: 9278: 8566: 8224: 7612: 7579: 7443:smallest elements, but unordered) and 7082:Bubble sort, and variants such as the 6862:). Finding the median, such as by the 3318:items to be sorted, with keys of size 3291:. These algorithms are not limited to 414:is the number of records to be sorted. 60:. The most frequently used orders are 27:Algorithm that arranges lists in order 9252: 8993: 8901:, New York: Academic Press, pp. 8648: 8592: 8586: 8515: 8503: 8382: 8370: 8342: 8139: 8088: 8086: 7594:from the original on 16 December 2014 7418: 7189: 4919:{\displaystyle n\cdot {\frac {k}{d}}} 4885:{\displaystyle n\cdot {\frac {k}{d}}} 4750:{\displaystyle n\cdot {\frac {k}{d}}} 4716:{\displaystyle n\cdot {\frac {k}{d}}} 4682:{\displaystyle n\cdot {\frac {k}{d}}} 4531:{\displaystyle n\cdot {\frac {k}{d}}} 4420:{\displaystyle n\cdot {\frac {k}{1}}} 4386:{\displaystyle n\cdot {\frac {k}{1}}} 4291:{\displaystyle n\cdot {\frac {k}{d}}} 4257:{\displaystyle n\cdot {\frac {k}{d}}} 4216:recursion levels, 2 for count array. 4141:{\displaystyle n\cdot {\frac {k}{d}}} 4107:{\displaystyle n\cdot {\frac {k}{d}}} 3446:in order to store them in the memory. 8406:from the original on 22 January 2018 8124: 8036: 7951:from the original on 9 December 2012 7824:. Vol. 4978. pp. 246–257. 7585: 6758:is a much more efficient version of 2268:Faster than bubble sort on average. 257:), with parallel sort in O(log 8789:from the original on 6 October 2012 8303: 7810:Ratio Based Stable In-Place Merging 7789:from the original on 23 August 2022 7617:(PhD thesis). Stanford University. 7501:, and rankings are determined by a 7403:-way merge similar to that used in 7376:For example, the popular recursive 7296:sorting algorithm that generalizes 6112:{\displaystyle n^{\Omega (\log n)}} 6067:{\displaystyle n^{\Omega (\log n)}} 6022:{\displaystyle n^{\Omega (\log n)}} 5931:{\displaystyle n^{\log 3/\log 1.5}} 5881:{\displaystyle n^{\log 3/\log 1.5}} 5831:{\displaystyle n^{\log 3/\log 1.5}} 1442:variant of heapsort based upon the 453: 24: 8980:A Comparison of Sorting Algorithms 8862: 8685: 8466:from the original on 14 April 2018 8083: 7399:), and the results merged using a 6643: 6089: 6044: 5999: 5973:Can be made stable, and is also a 5412: 4491:recursion levels, no count array. 4018:, then average time complexity is 3848:, then average time complexity is 3330:the range of numbers to be sorted. 3055: 25: 9751: 8919: 8569:Software: Practice and Experience 7872:(3 ed.). Pearson Education. 7369:speed (or, with caching, even at 6600: 6576: 3340:, where ≪ means "much less than". 1215:self-balancing binary search tree 232: 118:rather than one that allows only 8725:CodingUnit Programming Tutorials 8595:"A High-Speed Sorting Procedure" 8348:Algorithms & Data Structures 8013:"The Fastest Sorting Algorithm?" 7808:Kim, P. S.; Kutzner, A. (2008). 7505:instead of a sorting algorithm. 7485:), comparisons are very costly ( 7352:sorting approach, such as using 7222: 7169: 6512:implementations generally use a 5527: 5089: 4990:with unbounded run time and the 3433:{\displaystyle 2^{\frac {k}{d}}} 1342:in-place merge algorithm with a 385: 276:Swaps for "in-place" algorithms. 72:is important for optimizing the 9294:Computational complexity theory 8846:Fundamentals of Data Structures 8831: 8813:The Art of Computer Programming 8801: 8771: 8760:from the original on 2021-07-10 8742: 8731:from the original on 2021-07-10 8713: 8674:from the original on 2021-02-25 8654: 8642: 8560: 8521: 8509: 8497: 8448: 8418: 8388: 8376: 8364: 8336: 8297: 8256: 8218: 8191: 8180:from the original on 2020-09-29 8118: 8025:from the original on 2019-06-08 8004: 7963: 7933: 7568:from the original on 2018-10-08 6567: 3709:Also cannot sort non-integers. 3407:is limited to be not more than 1644:longest increasing subsequences 182:, can have better performance. 155:being first published in 2006. 9318: 7856: 7801: 7764: 7708: 7670: 7629: 7606: 7281: 7093: 7004: 6995: 6930: 6924: 6104: 6092: 6059: 6047: 6014: 6002: 5767: 5752: 5708: 5693: 5297:"I Can't Believe It Can Sort" 5147: 5141: 5114: 5108: 4209:{\displaystyle {\frac {k}{d}}} 4036: 4030: 4003: 3997: 3866: 3860: 3833: 3827: 3283:The following table describes 3035: 3029: 1327: 1321: 299: 13: 1: 8932: (archived 3 March 2015). 8707:10.1016/S0020-0190(00)00223-4 7544: 7306: 6687: 5773:{\displaystyle O(n\times n!)} 833:Partitioning & Selection 195:divide-and-conquer algorithms 76:of other algorithms (such as 8926:Sorting Algorithm Animations 8161:10.1007/978-3-540-72914-3_17 7840:10.1007/978-3-540-79228-4_22 7586:Lohr, Steve (Dec 17, 2001). 7463:) or one side (quickselect, 7328:digits each are sorted in O( 7133: 6953: 6805:divide-and-conquer algorithm 6789: 6142: 6137:divide-and-conquer algorithm 5980: 5784: 5714:{\displaystyle (n\times n!)} 5672: 5537: 5501: 5418: 5295: 5169: 5032: 4850: 4768: 4647: 4494: 4350: 4222: 4054: 3884: 3713: 3665:{\displaystyle n^{2}\cdot k} 3602: 3487: 3310:model as described below. 3164: 3053: 2909: 2820: 2732: 2644: 2556: 2468: 2380: 2271: 2158: 2029: 1912: 1762: 1664: 1551: 1453: 1349: 1220: 1095: 976: 843: 698: 582: 516: 333: 247:Best, worst and average case 215:best, worst and average case 7: 8200:Theory of Computing Systems 7508: 7340:(LSD) or starting from the 6744: 5647:{\displaystyle n\log ^{2}n} 558:{\displaystyle n\log ^{2}n} 229:is an open research topic. 10: 9756: 9602:Batcher odd–even mergesort 8545:Introduction to Algorithms 8322:10.1007/s00453-019-00626-0 8066:Introduction to Algorithms 7988:Introduction To Algorithms 7654:Introduction To Algorithms 7613:Demuth, Howard B. (1956). 7310: 7285: 7226: 7193: 7137: 7109: 6969: 6793: 6748: 6691: 6604: 6580: 6507:Popular sorting algorithms 6244: 6134: 5953: 5739: 5668: 5607:{\displaystyle \log ^{2}n} 5570:{\displaystyle \log ^{2}n} 5533: 5481: 5406: 5288: 5095: 4967: 4845: 4764: 4636: 4462: 4339: 4189: 3980: 3810: 3706: 3599:Cannot sort non-integers. 3598: 3314:Complexities below assume 3271: 3160: 3016: 2906: 2816: 2728: 2640: 2552: 2464: 2355: 2267: 2154: 2025: 1897: 1754: 1641: 1639:Insertion & Selection 1543: 1446:rather than a traditional 1437: 1308: 1212: 1091: 958: 835: 695: 578: 305:Whether or not they are a 9696: 9663: 9620: 9589: 9528: 9497: 9456: 9408: 9362: 9286: 9228: 9112: 9031: 8899:Computational Probability 8721:"Exchange Sort Algorithm" 8602:Communications of the ACM 8456:"sort – perldoc.perl.org" 8304:Han, Yijie (2020-04-01). 8281:10.1109/SFCS.2002.1181890 8212:10.1007/s00224-006-1311-1 7423:Related problems include 6680:(based on merge sort) or 5494:parallel processors. See 4981: 4344:to hold all of the bins. 300:stable sorting algorithms 261:), and bad behavior is O( 9607:Pairwise sorting network 8848:, H. Freeman & Co., 8426:"OpenJDK's TimSort.java" 8011:Nilsson, Stefan (2000). 7078:Bubble sort and variants 7072:operating system kernels 3692:{\displaystyle n\cdot k} 1541:Insertion & Merging 1306:Insertion & Merging 400:Comparison of algorithms 242:Computational complexity 151:dating to 2002, and the 52:that puts elements of a 18:Stable sorting algorithm 9635:Kirkpatrick–Reisch sort 9233:List of data structures 8271:. The 43rd Annual IEEE 7702:10.1093/comjnl/35.6.643 7615:Electronic Data Sorting 7431:of the correct order), 7338:least significant digit 6540:implementations and in 6224:{\displaystyle n\log n} 6192:{\displaystyle n\log n} 5496:spaghetti sort#Analysis 5266:{\displaystyle n\log n} 5232:{\displaystyle n\log n} 5198:{\displaystyle n\log n} 4953:{\displaystyle n+2^{d}} 4325:{\displaystyle n+2^{d}} 4175:{\displaystyle n+2^{d}} 3556:{\displaystyle n+2^{k}} 3522:{\displaystyle n+2^{k}} 2187:{\displaystyle n\log n} 2134:{\displaystyle n^{3/2}} 2096:{\displaystyle n^{4/3}} 2058:{\displaystyle n\log n} 1973:{\displaystyle n\log n} 1941:{\displaystyle n\log n} 1823:{\displaystyle n\log n} 1791:{\displaystyle n\log n} 1732:{\displaystyle n\log n} 1700:{\displaystyle n\log n} 1619:{\displaystyle n\log n} 1587:{\displaystyle n\log n} 1521:{\displaystyle n\log n} 1489:{\displaystyle n\log n} 1417:{\displaystyle n\log n} 1385:{\displaystyle n\log n} 1288:{\displaystyle n\log n} 1256:{\displaystyle n\log n} 1188:{\displaystyle n\log n} 1156:{\displaystyle n\log n} 1124:{\displaystyle n\log n} 1092:Variation of Heapsort. 1069:{\displaystyle n\log n} 1037:{\displaystyle n\log n} 1005:{\displaystyle n\log n} 936:{\displaystyle n\log n} 904:{\displaystyle n\log n} 872:{\displaystyle n\log n} 791:{\displaystyle n\log n} 759:{\displaystyle n\log n} 727:{\displaystyle n\log n} 675:{\displaystyle n\log n} 643:{\displaystyle n\log n} 611:{\displaystyle n\log n} 517: 421:is given for each case. 9515:Oscillating merge sort 9395:Proportion extend sort 9349:Transdichotomous model 8968:Ford–Johnson algorithm 8485:Merge sort in Java 1.3 8242:10.1006/jagm.2002.1211 7455:, which is related to 7342:most significant digit 7324:numbers consisting of 7107: 7011: 6967: 6940: 6488: 6414: 6357: 6225: 6193: 6161: 6144:Franceschini's method 6113: 6068: 6023: 5932: 5882: 5832: 5774: 5715: 5648: 5608: 5571: 5467: 5386: 5354: 5322: 5267: 5233: 5199: 5154: 5121: 5081: 4954: 4920: 4886: 4827: 4799: 4751: 4717: 4683: 4623: 4582: 4532: 4485: 4449: 4421: 4387: 4326: 4292: 4258: 4210: 4176: 4142: 4108: 4074: 4043: 4010: 3967: 3940: 3913: 3873: 3840: 3797: 3770: 3743: 3693: 3666: 3632: 3585: 3557: 3523: 3434: 3378: 3306:unless meet unit-cost 3252: 3222: 3192: 3141: 3111: 3081: 3042: 2997: 2967: 2937: 2885: 2855: 2797: 2767: 2709: 2679: 2621: 2591: 2533: 2503: 2445: 2415: 2336: 2306: 2248: 2218: 2188: 2135: 2097: 2059: 2004: 1974: 1942: 1883: 1882:{\displaystyle \log n} 1854: 1824: 1792: 1733: 1701: 1620: 1588: 1522: 1490: 1418: 1386: 1334: 1309:Combine a block-based 1289: 1257: 1189: 1157: 1125: 1070: 1038: 1006: 937: 905: 873: 821: 820:{\displaystyle \log n} 792: 760: 728: 676: 644: 612: 559: 344: 223:upper and lower bounds 37: 9676:Pre-topological order 8874:Sorting and Searching 8818:Sorting and Searching 8614:10.1145/368370.368387 8593:Shell, D. L. (1959). 8533:Leiserson, Charles E. 8230:Journal of Algorithms 8053:Leiserson, Charles E. 7975:Leiserson, Charles E. 7919:10.1145/359619.359631 7748:10.1145/800061.808726 7641:Leiserson, Charles E. 7526:Schwartzian transform 7213:distributed algorithm 7101: 7012: 7010:{\displaystyle O(kn)} 6961: 6941: 6774:) time, instead of O( 6557:locality of reference 6489: 6415: 6358: 6226: 6194: 6162: 6114: 6069: 6024: 5933: 5883: 5833: 5775: 5716: 5649: 5609: 5572: 5468: 5466:{\displaystyle n^{2}} 5421:Spaghetti (Poll) sort 5387: 5385:{\displaystyle n^{2}} 5355: 5353:{\displaystyle n^{2}} 5323: 5321:{\displaystyle n^{2}} 5268: 5234: 5200: 5155: 5122: 5082: 5080:{\displaystyle n^{2}} 4955: 4921: 4887: 4828: 4826:{\displaystyle n^{2}} 4800: 4752: 4718: 4684: 4624: 4583: 4533: 4486: 4450: 4448:{\displaystyle 2^{1}} 4422: 4388: 4327: 4293: 4259: 4211: 4177: 4143: 4109: 4075: 4044: 4011: 3968: 3941: 3914: 3874: 3841: 3798: 3771: 3744: 3694: 3667: 3633: 3586: 3584:{\displaystyle 2^{k}} 3558: 3524: 3453:Non-comparison sorts 3435: 3379: 3345:random-access machine 3308:random-access machine 3253: 3251:{\displaystyle n^{2}} 3223: 3221:{\displaystyle n^{2}} 3193: 3191:{\displaystyle n^{2}} 3142: 3140:{\displaystyle n^{2}} 3112: 3110:{\displaystyle n^{2}} 3082: 3080:{\displaystyle n^{2}} 3043: 2998: 2996:{\displaystyle n^{2}} 2968: 2966:{\displaystyle n^{2}} 2938: 2936:{\displaystyle n^{2}} 2886: 2884:{\displaystyle n^{2}} 2856: 2854:{\displaystyle n^{2}} 2798: 2796:{\displaystyle n^{2}} 2768: 2766:{\displaystyle n^{2}} 2710: 2708:{\displaystyle n^{2}} 2680: 2678:{\displaystyle n^{2}} 2622: 2620:{\displaystyle n^{2}} 2592: 2590:{\displaystyle n^{2}} 2534: 2532:{\displaystyle n^{2}} 2504: 2502:{\displaystyle n^{2}} 2446: 2444:{\displaystyle n^{2}} 2416: 2414:{\displaystyle n^{2}} 2337: 2335:{\displaystyle n^{2}} 2307: 2305:{\displaystyle n^{2}} 2249: 2247:{\displaystyle n^{2}} 2219: 2217:{\displaystyle n^{2}} 2189: 2136: 2098: 2060: 2005: 2003:{\displaystyle n^{2}} 1975: 1943: 1884: 1855: 1853:{\displaystyle n^{2}} 1825: 1793: 1734: 1702: 1621: 1589: 1523: 1491: 1419: 1387: 1335: 1290: 1258: 1190: 1158: 1126: 1071: 1039: 1007: 960:Highly parallelizable 938: 906: 874: 822: 793: 761: 729: 677: 645: 613: 560: 464:Mathematical analysis 341: 211:randomized algorithms 66:lexicographical order 33: 9655:Merge-insertion sort 9520:Polyphase merge sort 9375:Cocktail shaker sort 9130:Breadth-first search 8754:JavaBitsNotebook.com 8275:. pp. 135–144. 8094:Goodrich, Michael T. 7866:(1 September 1998). 7476:Fisher–Yates shuffle 7465:decrease-and-conquer 6989: 6896: 6884:If a guarantee of O( 6766:, a special type of 6432: 6378: 6315: 6206: 6174: 6151: 6081: 6036: 5991: 5895: 5845: 5795: 5746: 5690: 5622: 5585: 5548: 5450: 5369: 5337: 5305: 5248: 5214: 5180: 5172:Merge-insertion sort 5153:{\displaystyle O(S)} 5135: 5120:{\displaystyle O(n)} 5102: 5064: 4931: 4897: 4863: 4810: 4783: 4728: 4694: 4660: 4593: 4543: 4509: 4467: 4432: 4398: 4364: 4303: 4269: 4235: 4193: 4153: 4119: 4085: 4064: 4042:{\displaystyle O(n)} 4024: 4009:{\displaystyle O(n)} 3991: 3951: 3924: 3897: 3872:{\displaystyle O(n)} 3854: 3839:{\displaystyle O(n)} 3821: 3781: 3754: 3727: 3677: 3643: 3616: 3568: 3534: 3500: 3412: 3353: 3279:Non-comparison sorts 3235: 3205: 3175: 3124: 3094: 3064: 3041:{\displaystyle O(n)} 3023: 2980: 2950: 2920: 2868: 2838: 2780: 2750: 2692: 2662: 2604: 2574: 2516: 2486: 2471:Cocktail shaker sort 2428: 2398: 2319: 2289: 2231: 2201: 2169: 2110: 2072: 2040: 1987: 1955: 1923: 1867: 1837: 1805: 1773: 1714: 1682: 1601: 1569: 1503: 1471: 1399: 1367: 1344:bottom-up merge sort 1333:{\displaystyle O(n)} 1315: 1270: 1238: 1170: 1138: 1106: 1051: 1019: 987: 918: 886: 854: 805: 773: 741: 709: 657: 625: 593: 533: 458:Below is a table of 219:time–space tradeoffs 126:History and concepts 9671:Topological sorting 9433:Cartesian tree sort 9220:Topological sorting 9150:Dynamic programming 8695:Inf. Process. Lett. 7472:shuffling algorithm 7425:approximate sorting 7386:relational database 6867:selection algorithm 4798:{\displaystyle n+r} 4484:{\displaystyle k/1} 3966:{\displaystyle n+r} 3939:{\displaystyle n+r} 3912:{\displaystyle n+r} 3796:{\displaystyle n+r} 3769:{\displaystyle n+r} 3742:{\displaystyle n+r} 3631:{\displaystyle n+k} 3454: 2735:Simple pancake sort 519:In-place merge sort 488: 9735:Sorting algorithms 9561:Interpolation sort 9536:American flag sort 9529:Distribution sorts 9510:Cascade merge sort 9280:Sorting algorithms 9238:List of algorithms 9145:Divide and conquer 9140:Depth-first search 9135:Brute-force search 9049:Binary search tree 8491:2009-03-04 at the 8385:, pp. 101–102 7780:Dbs.uni-leipzig.de 7773:"Sortierverfahren" 7461:divide-and-conquer 7435:(sorting only the 7419:Related algorithms 7294:divide-and-conquer 7190:Distribution sorts 7108: 7007: 6968: 6964:swapping positions 6936: 6807:which relies on a 6549:distribution sorts 6484: 6410: 6363:expected time and 6353: 6279:Thorup's algorithm 6221: 6189: 6157: 6109: 6064: 6019: 5928: 5878: 5828: 5770: 5711: 5644: 5604: 5567: 5463: 5382: 5350: 5318: 5263: 5229: 5195: 5150: 5117: 5077: 4950: 4916: 4882: 4823: 4795: 4747: 4713: 4679: 4619: 4578: 4528: 4481: 4463:d=1 for in-place, 4445: 4417: 4383: 4322: 4288: 4254: 4206: 4172: 4138: 4104: 4070: 4039: 4006: 3963: 3936: 3909: 3869: 3836: 3793: 3766: 3739: 3689: 3662: 3628: 3581: 3553: 3519: 3452: 3430: 3374: 3373: 3248: 3218: 3188: 3137: 3107: 3077: 3038: 2993: 2963: 2933: 2881: 2851: 2793: 2763: 2705: 2675: 2617: 2587: 2529: 2499: 2441: 2411: 2332: 2302: 2244: 2214: 2184: 2131: 2093: 2055: 2000: 1970: 1938: 1879: 1850: 1820: 1788: 1729: 1697: 1616: 1584: 1518: 1486: 1414: 1382: 1330: 1285: 1253: 1185: 1153: 1121: 1066: 1034: 1002: 933: 901: 869: 817: 788: 756: 724: 672: 640: 608: 555: 484: 345: 38: 9722: 9721: 9697:Impractical sorts 9246: 9245: 9044:Associative array 8891:Sedgewick, Robert 8662:"kernel/groups.c" 8537:Rivest, Ronald L. 8529:Cormen, Thomas H. 8436:on 14 August 2011 8170:978-3-540-72913-6 8111:978-0-471-38365-9 8098:Tamassia, Roberto 8057:Rivest, Ronald L. 8049:Cormen, Thomas H. 7979:Rivest, Ronald L. 7971:Cormen, Thomas H. 7879:978-81-317-1291-7 7864:Sedgewick, Robert 7849:978-3-540-79227-7 7664:978-0-262-03293-3 7645:Rivest, Ronald L. 7637:Cormen, Thomas H. 7521:K-sorted sequence 7503:tournament system 7499:Elo rating system 7292:Bucket sort is a 7201:Distribution sort 6864:median of medians 6477: 6403: 6346: 6311:algorithm taking 6260: 6259: 6160:{\displaystyle -} 4972: 4971: 4914: 4880: 4745: 4711: 4677: 4604: 4565: 4526: 4415: 4381: 4286: 4252: 4204: 4136: 4102: 4073:{\displaystyle n} 3427: 3402: 3371: 3343:In the unit-cost 3276: 3275: 2155:Small code size. 1444:Leonardo sequence 840:implementations. 120:sequential access 95:The output is in 46:sorting algorithm 16:(Redirected from 9747: 9630:Block merge sort 9590:Concurrent sorts 9489:Patience sorting 9273: 9266: 9259: 9250: 9249: 9215:String-searching 9014: 9007: 9000: 8991: 8990: 8915: 8886: 8870:Knuth, Donald E. 8857: 8835: 8829: 8805: 8799: 8798: 8796: 8794: 8775: 8769: 8768: 8766: 8765: 8746: 8740: 8739: 8737: 8736: 8717: 8711: 8710: 8689: 8683: 8682: 8680: 8679: 8658: 8652: 8651:, pp. 81–82 8646: 8640: 8639: 8637: 8636: 8630: 8624:. Archived from 8599: 8590: 8584: 8583: 8564: 8558: 8557: 8525: 8519: 8513: 8507: 8506:, pp. 87–89 8501: 8495: 8482: 8476: 8475: 8473: 8471: 8460:perldoc.perl.org 8452: 8446: 8445: 8443: 8441: 8432:. Archived from 8422: 8416: 8415: 8413: 8411: 8392: 8386: 8380: 8374: 8373:, pp. 79–80 8368: 8362: 8361: 8340: 8334: 8333: 8301: 8295: 8294: 8260: 8254: 8253: 8222: 8216: 8215: 8195: 8189: 8187: 8186: 8185: 8179: 8154: 8143: 8137: 8136: 8134: 8122: 8116: 8115: 8090: 8081: 8080: 8045: 8034: 8033: 8031: 8030: 8008: 8002: 8001: 7967: 7961: 7960: 7958: 7956: 7937: 7931: 7930: 7897: 7891: 7890: 7888: 7886: 7860: 7854: 7853: 7833: 7805: 7799: 7798: 7796: 7794: 7788: 7777: 7768: 7762: 7761: 7742:. pp. 1–9. 7731: 7712: 7706: 7705: 7695: 7674: 7668: 7667: 7633: 7627: 7626: 7610: 7604: 7603: 7601: 7599: 7583: 7577: 7576: 7574: 7573: 7554: 7532:Search algorithm 7393:external sorting 7257:| and using the 7249:|) memory where 7217:external sorting 7196:External sorting 7186:will be faster. 7068:embedded systems 7018: 7016: 7014: 7013: 7008: 6979:was invented by 6945: 6943: 6942: 6937: 6920: 6919: 6869:is however an O( 6514:hybrid algorithm 6493: 6491: 6490: 6485: 6483: 6479: 6478: 6461: 6459: 6419: 6417: 6416: 6411: 6409: 6405: 6404: 6393: 6362: 6360: 6359: 6354: 6352: 6348: 6347: 6330: 6295: 6255: 6236: 6231: 6230: 6228: 6227: 6222: 6199: 6198: 6196: 6195: 6190: 6167: 6166: 6164: 6163: 6158: 6126: 6125: 6119: 6118: 6116: 6115: 6110: 6108: 6107: 6074: 6073: 6071: 6070: 6065: 6063: 6062: 6029: 6028: 6026: 6025: 6020: 6018: 6017: 5972: 5945: 5944: 5938: 5937: 5935: 5934: 5929: 5927: 5926: 5916: 5888: 5887: 5885: 5884: 5879: 5877: 5876: 5866: 5838: 5837: 5835: 5834: 5829: 5827: 5826: 5816: 5779: 5777: 5776: 5771: 5731: 5726: 5721: 5720: 5718: 5717: 5712: 5683: 5682: 5660: 5655: 5653: 5651: 5650: 5645: 5637: 5636: 5615: 5613: 5611: 5610: 5605: 5597: 5596: 5578: 5576: 5574: 5573: 5568: 5560: 5559: 5525: 5520: 5515: 5510: 5473: 5472: 5470: 5469: 5464: 5462: 5461: 5443: 5442: 5436: 5435: 5429: 5428: 5398: 5393: 5392: 5391: 5389: 5388: 5383: 5381: 5380: 5361: 5360: 5359: 5357: 5356: 5351: 5349: 5348: 5329: 5328: 5327: 5325: 5324: 5319: 5317: 5316: 5280: 5275: 5272: 5270: 5269: 5264: 5241: 5238: 5236: 5235: 5230: 5207: 5204: 5202: 5201: 5196: 5165: 5161: 5159: 5157: 5156: 5151: 5128: 5126: 5124: 5123: 5118: 5087: 5086: 5084: 5083: 5078: 5076: 5075: 5057: 5056: 5050: 5049: 5043: 5042: 5005: 5004: 4959: 4957: 4956: 4951: 4949: 4948: 4925: 4923: 4922: 4917: 4915: 4907: 4891: 4889: 4888: 4883: 4881: 4873: 4837: 4832: 4830: 4829: 4824: 4822: 4821: 4804: 4802: 4801: 4796: 4777: 4756: 4754: 4753: 4748: 4746: 4738: 4722: 4720: 4719: 4714: 4712: 4704: 4688: 4686: 4685: 4680: 4678: 4670: 4643: 4628: 4626: 4625: 4620: 4618: 4617: 4605: 4597: 4587: 4585: 4584: 4579: 4577: 4573: 4566: 4558: 4537: 4535: 4534: 4529: 4527: 4519: 4503: 4490: 4488: 4487: 4482: 4477: 4454: 4452: 4451: 4446: 4444: 4443: 4426: 4424: 4423: 4418: 4416: 4408: 4392: 4390: 4389: 4384: 4382: 4374: 4343: 4331: 4329: 4328: 4323: 4321: 4320: 4297: 4295: 4294: 4289: 4287: 4279: 4263: 4261: 4260: 4255: 4253: 4245: 4215: 4213: 4212: 4207: 4205: 4197: 4181: 4179: 4178: 4173: 4171: 4170: 4147: 4145: 4144: 4139: 4137: 4129: 4113: 4111: 4110: 4105: 4103: 4095: 4079: 4077: 4076: 4071: 4050: 4048: 4046: 4045: 4040: 4017: 4015: 4013: 4012: 4007: 3972: 3970: 3969: 3964: 3945: 3943: 3942: 3937: 3918: 3916: 3915: 3910: 3880: 3878: 3876: 3875: 3870: 3847: 3845: 3843: 3842: 3837: 3802: 3800: 3799: 3794: 3775: 3773: 3772: 3767: 3748: 3746: 3745: 3740: 3698: 3696: 3695: 3690: 3671: 3669: 3668: 3663: 3655: 3654: 3637: 3635: 3634: 3629: 3590: 3588: 3587: 3582: 3580: 3579: 3562: 3560: 3559: 3554: 3552: 3551: 3528: 3526: 3525: 3520: 3518: 3517: 3481: 3455: 3451: 3445: 3439: 3437: 3436: 3431: 3429: 3428: 3420: 3406: 3400: 3388: 3383: 3381: 3380: 3375: 3372: 3364: 3339: 3329: 3325: 3321: 3317: 3289:comparison sorts 3263: 3258: 3257: 3255: 3254: 3249: 3247: 3246: 3228: 3227: 3225: 3224: 3219: 3217: 3216: 3198: 3197: 3195: 3194: 3189: 3187: 3186: 3161:Tiny code size. 3152: 3147: 3146: 3144: 3143: 3138: 3136: 3135: 3117: 3116: 3114: 3113: 3108: 3106: 3105: 3087: 3086: 3084: 3083: 3078: 3076: 3075: 3049: 3047: 3045: 3044: 3039: 3008: 3003: 3002: 3000: 2999: 2994: 2992: 2991: 2973: 2972: 2970: 2969: 2964: 2962: 2961: 2943: 2942: 2940: 2939: 2934: 2932: 2931: 2898: 2897: 2891: 2890: 2888: 2887: 2882: 2880: 2879: 2861: 2860: 2858: 2857: 2852: 2850: 2849: 2831: 2830: 2808: 2803: 2802: 2800: 2799: 2794: 2792: 2791: 2773: 2772: 2770: 2769: 2764: 2762: 2761: 2743: 2742: 2720: 2715: 2714: 2712: 2711: 2706: 2704: 2703: 2685: 2684: 2682: 2681: 2676: 2674: 2673: 2655: 2654: 2641:Tiny code size. 2632: 2627: 2626: 2624: 2623: 2618: 2616: 2615: 2597: 2596: 2594: 2593: 2588: 2586: 2585: 2567: 2566: 2544: 2539: 2538: 2536: 2535: 2530: 2528: 2527: 2509: 2508: 2506: 2505: 2500: 2498: 2497: 2479: 2478: 2465:Tiny code size. 2456: 2451: 2450: 2448: 2447: 2442: 2440: 2439: 2421: 2420: 2418: 2417: 2412: 2410: 2409: 2391: 2390: 2369: 2347: 2342: 2341: 2339: 2338: 2333: 2331: 2330: 2312: 2311: 2309: 2308: 2303: 2301: 2300: 2282: 2281: 2259: 2254: 2253: 2251: 2250: 2245: 2243: 2242: 2224: 2223: 2221: 2220: 2215: 2213: 2212: 2194: 2193: 2191: 2190: 2185: 2146: 2141: 2140: 2138: 2137: 2132: 2130: 2129: 2125: 2103: 2102: 2100: 2099: 2094: 2092: 2091: 2087: 2065: 2064: 2062: 2061: 2056: 2017: 2016: 2010: 2009: 2007: 2006: 2001: 1999: 1998: 1980: 1979: 1977: 1976: 1971: 1948: 1947: 1945: 1944: 1939: 1908: 1889: 1888: 1886: 1885: 1880: 1860: 1859: 1857: 1856: 1851: 1849: 1848: 1830: 1829: 1827: 1826: 1821: 1798: 1797: 1795: 1794: 1789: 1746: 1745: 1739: 1738: 1736: 1735: 1730: 1707: 1706: 1704: 1703: 1698: 1675: 1674: 1660: 1633: 1632: 1626: 1625: 1623: 1622: 1617: 1594: 1593: 1591: 1590: 1585: 1562: 1561: 1554:Patience sorting 1535: 1534: 1528: 1527: 1525: 1524: 1519: 1496: 1495: 1493: 1492: 1487: 1464: 1463: 1429: 1424: 1423: 1421: 1420: 1415: 1392: 1391: 1389: 1388: 1383: 1360: 1359: 1341: 1339: 1337: 1336: 1331: 1300: 1295: 1294: 1292: 1291: 1286: 1263: 1262: 1260: 1259: 1254: 1231: 1230: 1204: 1203: 1197: 1195: 1194: 1192: 1191: 1186: 1163: 1162: 1160: 1159: 1154: 1131: 1130: 1128: 1127: 1122: 1083: 1082: 1076: 1075: 1073: 1072: 1067: 1044: 1043: 1041: 1040: 1035: 1012: 1011: 1009: 1008: 1003: 972: 950: 949: 943: 942: 940: 939: 934: 911: 910: 908: 907: 902: 879: 878: 876: 875: 870: 836:Used in several 827: 826: 824: 823: 818: 798: 797: 795: 794: 789: 766: 765: 763: 762: 757: 734: 733: 731: 730: 725: 687: 682: 681: 679: 678: 673: 650: 649: 647: 646: 641: 618: 617: 615: 614: 609: 570: 565: 564: 562: 561: 556: 548: 547: 489: 486:Comparison sorts 483: 480: 460:comparison sorts 454:Comparison sorts 448: 440: 413: 389: 381: 377: 187:computer science 135:, who worked on 102:The output is a 42:computer science 21: 9755: 9754: 9750: 9749: 9748: 9746: 9745: 9744: 9740:Data processing 9725: 9724: 9723: 9718: 9692: 9683:Pancake sorting 9659: 9616: 9585: 9566:Pigeonhole sort 9524: 9493: 9457:Insertion sorts 9452: 9438:Tournament sort 9410:Selection sorts 9404: 9358: 9339:Integer sorting 9334:Sorting network 9324:Comparison sort 9282: 9277: 9247: 9242: 9224: 9155:Graph traversal 9108: 9032:Data structures 9027: 9021:Data structures 9018: 8966:– Performed by 8930:Wayback Machine 8922: 8913: 8889: 8884: 8868: 8865: 8863:Further reading 8860: 8836: 8832: 8806: 8802: 8792: 8790: 8777: 8776: 8772: 8763: 8761: 8750:"Exchange Sort" 8748: 8747: 8743: 8734: 8732: 8719: 8718: 8714: 8690: 8686: 8677: 8675: 8660: 8659: 8655: 8647: 8643: 8634: 8632: 8628: 8597: 8591: 8587: 8565: 8561: 8555: 8541:Stein, Clifford 8526: 8522: 8514: 8510: 8502: 8498: 8493:Wayback Machine 8483: 8479: 8469: 8467: 8454: 8453: 8449: 8439: 8437: 8424: 8423: 8419: 8409: 8407: 8394: 8393: 8389: 8381: 8377: 8369: 8365: 8358: 8341: 8337: 8302: 8298: 8291: 8261: 8257: 8223: 8219: 8196: 8192: 8183: 8181: 8177: 8171: 8152: 8144: 8140: 8123: 8119: 8112: 8091: 8084: 8077: 8061:Stein, Clifford 8046: 8037: 8028: 8026: 8009: 8005: 7999: 7983:Stein, Clifford 7968: 7964: 7954: 7952: 7939: 7938: 7934: 7913:(10): 847–857. 7898: 7894: 7884: 7882: 7880: 7861: 7857: 7850: 7831:10.1.1.330.2641 7806: 7802: 7792: 7790: 7786: 7775: 7771:Prof. E. Rahm. 7769: 7765: 7758: 7732:sorting network 7729: 7713: 7709: 7675: 7671: 7665: 7649:Stein, Clifford 7634: 7630: 7611: 7607: 7597: 7595: 7584: 7580: 7571: 7569: 7556: 7555: 7551: 7547: 7511: 7447:(computing the 7433:partial sorting 7421: 7362: 7315: 7309: 7290: 7284: 7231: 7225: 7198: 7192: 7172: 7142: 7136: 7114: 7096: 7080: 6990: 6987: 6986: 6984: 6974: 6956: 6915: 6911: 6897: 6894: 6893: 6881:) performance. 6877: log 6858: log 6798: 6792: 6753: 6747: 6696: 6690: 6646: 6644:Efficient sorts 6619:comparison sort 6609: 6603: 6585: 6579: 6570: 6509: 6460: 6455: 6442: 6438: 6433: 6430: 6429: 6392: 6388: 6384: 6379: 6376: 6375: 6329: 6325: 6321: 6316: 6313: 6312: 6309:integer sorting 6282: 6246: 6207: 6204: 6203: 6175: 6172: 6171: 6152: 6149: 6148: 6123: 6088: 6084: 6082: 6079: 6078: 6043: 6039: 6037: 6034: 6033: 5998: 5994: 5992: 5989: 5988: 5975:sorting network 5955: 5942: 5912: 5902: 5898: 5896: 5893: 5892: 5862: 5852: 5848: 5846: 5843: 5842: 5812: 5802: 5798: 5796: 5793: 5792: 5747: 5744: 5743: 5691: 5688: 5687: 5680: 5632: 5628: 5623: 5620: 5619: 5592: 5588: 5586: 5583: 5582: 5555: 5551: 5549: 5546: 5545: 5504:Sorting network 5457: 5453: 5451: 5448: 5447: 5440: 5433: 5426: 5376: 5372: 5370: 5367: 5366: 5365: 5344: 5340: 5338: 5335: 5334: 5333: 5312: 5308: 5306: 5303: 5302: 5301: 5273: 5249: 5246: 5245: 5239: 5215: 5212: 5211: 5205: 5181: 5178: 5177: 5163: 5136: 5133: 5132: 5130: 5103: 5100: 5099: 5097: 5071: 5067: 5065: 5062: 5061: 5054: 5047: 5040: 4984: 4944: 4940: 4932: 4929: 4928: 4906: 4898: 4895: 4894: 4872: 4864: 4861: 4860: 4835: 4817: 4813: 4811: 4808: 4807: 4784: 4781: 4780: 4775: 4737: 4729: 4726: 4725: 4703: 4695: 4692: 4691: 4669: 4661: 4658: 4657: 4638: 4613: 4609: 4596: 4594: 4591: 4590: 4557: 4556: 4552: 4544: 4541: 4540: 4518: 4510: 4507: 4506: 4501: 4473: 4468: 4465: 4464: 4439: 4435: 4433: 4430: 4429: 4407: 4399: 4396: 4395: 4373: 4365: 4362: 4361: 4341: 4316: 4312: 4304: 4301: 4300: 4278: 4270: 4267: 4266: 4244: 4236: 4233: 4232: 4196: 4194: 4191: 4190: 4166: 4162: 4154: 4151: 4150: 4128: 4120: 4117: 4116: 4094: 4086: 4083: 4082: 4065: 4062: 4061: 4025: 4022: 4021: 4019: 3992: 3989: 3988: 3986: 3952: 3949: 3948: 3925: 3922: 3921: 3898: 3895: 3894: 3855: 3852: 3851: 3849: 3822: 3819: 3818: 3816: 3782: 3779: 3778: 3755: 3752: 3751: 3728: 3725: 3724: 3718:(integer keys) 3678: 3675: 3674: 3650: 3646: 3644: 3641: 3640: 3617: 3614: 3613: 3607:(uniform keys) 3575: 3571: 3569: 3566: 3565: 3547: 3543: 3535: 3532: 3531: 3513: 3509: 3501: 3498: 3497: 3490:Pigeonhole sort 3476: 3443: 3441: 3419: 3415: 3413: 3410: 3409: 3404: 3401: 3390: 3386: 3385: 3363: 3354: 3351: 3350: 3334: 3327: 3323: 3319: 3315: 3285:integer sorting 3281: 3242: 3238: 3236: 3233: 3232: 3212: 3208: 3206: 3203: 3202: 3182: 3178: 3176: 3173: 3172: 3131: 3127: 3125: 3122: 3121: 3101: 3097: 3095: 3092: 3091: 3071: 3067: 3065: 3062: 3061: 3024: 3021: 3020: 3018: 2987: 2983: 2981: 2978: 2977: 2957: 2953: 2951: 2948: 2947: 2927: 2923: 2921: 2918: 2917: 2895: 2875: 2871: 2869: 2866: 2865: 2845: 2841: 2839: 2836: 2835: 2828: 2787: 2783: 2781: 2778: 2777: 2757: 2753: 2751: 2748: 2747: 2740: 2699: 2695: 2693: 2690: 2689: 2669: 2665: 2663: 2660: 2659: 2652: 2611: 2607: 2605: 2602: 2601: 2581: 2577: 2575: 2572: 2571: 2564: 2523: 2519: 2517: 2514: 2513: 2493: 2489: 2487: 2484: 2483: 2476: 2435: 2431: 2429: 2426: 2425: 2405: 2401: 2399: 2396: 2395: 2388: 2356: 2326: 2322: 2320: 2317: 2316: 2296: 2292: 2290: 2287: 2286: 2279: 2238: 2234: 2232: 2229: 2228: 2208: 2204: 2202: 2199: 2198: 2170: 2167: 2166: 2121: 2117: 2113: 2111: 2108: 2107: 2083: 2079: 2075: 2073: 2070: 2069: 2041: 2038: 2037: 2014: 1994: 1990: 1988: 1985: 1984: 1956: 1953: 1952: 1924: 1921: 1920: 1899: 1868: 1865: 1864: 1844: 1840: 1838: 1835: 1834: 1806: 1803: 1802: 1774: 1771: 1770: 1743: 1715: 1712: 1711: 1683: 1680: 1679: 1672: 1647: 1630: 1602: 1599: 1598: 1570: 1567: 1566: 1559: 1532: 1504: 1501: 1500: 1472: 1469: 1468: 1461: 1400: 1397: 1396: 1368: 1365: 1364: 1357: 1316: 1313: 1312: 1310: 1271: 1268: 1267: 1239: 1236: 1235: 1228: 1201: 1171: 1168: 1167: 1139: 1136: 1135: 1107: 1104: 1103: 1080: 1052: 1049: 1048: 1020: 1017: 1016: 988: 985: 984: 979:Tournament sort 963: 947: 919: 916: 915: 887: 884: 883: 855: 852: 851: 806: 803: 802: 774: 771: 770: 742: 739: 738: 710: 707: 706: 658: 655: 654: 626: 623: 622: 594: 591: 590: 543: 539: 534: 531: 530: 467: 456: 442: 435: 419:time complexity 411: 402: 379: 375: 336: 307:comparison sort 253: log 235: 199:data structures 133:Betty Holberton 128: 62:numerical order 28: 23: 22: 15: 12: 11: 5: 9753: 9743: 9742: 9737: 9720: 9719: 9717: 9716: 9711: 9706: 9700: 9698: 9694: 9693: 9691: 9690: 9688:Spaghetti sort 9685: 9680: 9679: 9678: 9667: 9665: 9661: 9660: 9658: 9657: 9652: 9647: 9642: 9637: 9632: 9626: 9624: 9618: 9617: 9615: 9614: 9609: 9604: 9599: 9597:Bitonic sorter 9593: 9591: 9587: 9586: 9584: 9583: 9578: 9573: 9568: 9563: 9558: 9553: 9548: 9543: 9538: 9532: 9530: 9526: 9525: 9523: 9522: 9517: 9512: 9507: 9501: 9499: 9495: 9494: 9492: 9491: 9486: 9481: 9476: 9471: 9466: 9464:Insertion sort 9460: 9458: 9454: 9453: 9451: 9450: 9448:Weak-heap sort 9445: 9440: 9435: 9430: 9425: 9420: 9418:Selection sort 9414: 9412: 9406: 9405: 9403: 9402: 9397: 9392: 9387: 9382: 9377: 9372: 9366: 9364: 9363:Exchange sorts 9360: 9359: 9357: 9356: 9351: 9346: 9341: 9336: 9331: 9326: 9321: 9316: 9311: 9306: 9301: 9299:Big O notation 9296: 9290: 9288: 9284: 9283: 9276: 9275: 9268: 9261: 9253: 9244: 9243: 9241: 9240: 9235: 9229: 9226: 9225: 9223: 9222: 9217: 9212: 9207: 9202: 9197: 9192: 9187: 9182: 9177: 9172: 9167: 9162: 9157: 9152: 9147: 9142: 9137: 9132: 9127: 9122: 9116: 9114: 9110: 9109: 9107: 9106: 9101: 9096: 9091: 9086: 9081: 9076: 9071: 9066: 9061: 9056: 9051: 9046: 9041: 9035: 9033: 9029: 9028: 9017: 9016: 9009: 9002: 8994: 8988: 8987: 8977: 8971: 8961: 8955: 8945: 8939: 8933: 8921: 8920:External links 8918: 8917: 8916: 8911: 8887: 8882: 8864: 8861: 8859: 8858: 8838:Ellis Horowitz 8830: 8800: 8770: 8741: 8712: 8701:(5): 223–227. 8684: 8653: 8641: 8585: 8575:(8): 983–993, 8559: 8554:978-0262033848 8553: 8520: 8508: 8496: 8477: 8447: 8417: 8387: 8375: 8363: 8357:978-0130220059 8356: 8344:Wirth, Niklaus 8335: 8316:(4): 966–978. 8296: 8289: 8255: 8236:(2): 205–230. 8217: 8206:(4): 327–353. 8190: 8169: 8138: 8117: 8110: 8082: 8075: 8035: 8003: 7997: 7962: 7932: 7892: 7878: 7855: 7848: 7800: 7763: 7756: 7707: 7693:10.1.1.54.8381 7686:(6): 643–650. 7669: 7663: 7628: 7605: 7578: 7564:. 2013-10-13. 7548: 7546: 7543: 7542: 7541: 7535: 7529: 7523: 7518: 7510: 7507: 7491:search engines 7483:voting systems 7420: 7417: 7413:virtual memory 7361: 7358: 7354:insertion sort 7311:Main article: 7308: 7305: 7286:Main article: 7283: 7280: 7245:) time and O(| 7227:Main article: 7224: 7221: 7191: 7188: 7184:insertion sort 7171: 7168: 7138:Main article: 7135: 7132: 7110:Main article: 7095: 7092: 7079: 7076: 7006: 7003: 7000: 6997: 6994: 6970:Main article: 6955: 6952: 6935: 6932: 6929: 6926: 6923: 6918: 6914: 6910: 6907: 6904: 6901: 6794:Main article: 6791: 6788: 6760:selection sort 6749:Main article: 6746: 6743: 6692:Main article: 6689: 6686: 6645: 6642: 6631:insertion sort 6612:Selection sort 6607:Selection sort 6605:Main article: 6602: 6601:Selection sort 6599: 6589:Insertion sort 6583:Insertion sort 6581:Main article: 6578: 6577:Insertion sort 6575: 6569: 6566: 6508: 6505: 6504: 6503: 6482: 6476: 6473: 6470: 6467: 6464: 6458: 6454: 6451: 6448: 6445: 6441: 6437: 6408: 6402: 6399: 6396: 6391: 6387: 6383: 6372: 6351: 6345: 6342: 6339: 6336: 6333: 6328: 6324: 6320: 6305: 6258: 6257: 6243: 6240: 6237: 6232: 6220: 6217: 6214: 6211: 6200: 6188: 6185: 6182: 6179: 6168: 6156: 6145: 6141: 6140: 6133: 6130: 6127: 6120: 6106: 6103: 6100: 6097: 6094: 6091: 6087: 6075: 6061: 6058: 6055: 6052: 6049: 6046: 6042: 6030: 6016: 6013: 6010: 6007: 6004: 6001: 5997: 5985: 5979: 5978: 5952: 5949: 5946: 5939: 5925: 5922: 5919: 5915: 5911: 5908: 5905: 5901: 5889: 5875: 5872: 5869: 5865: 5861: 5858: 5855: 5851: 5839: 5825: 5822: 5819: 5815: 5811: 5808: 5805: 5801: 5789: 5783: 5782: 5769: 5766: 5763: 5760: 5757: 5754: 5751: 5738: 5735: 5732: 5727: 5722: 5710: 5707: 5704: 5701: 5698: 5695: 5684: 5677: 5671: 5670: 5667: 5664: 5661: 5656: 5643: 5640: 5635: 5631: 5627: 5616: 5603: 5600: 5595: 5591: 5579: 5566: 5563: 5558: 5554: 5542: 5540:Bitonic sorter 5536: 5535: 5532: 5529: 5526: 5521: 5516: 5511: 5506: 5500: 5499: 5480: 5477: 5474: 5460: 5456: 5444: 5437: 5430: 5423: 5417: 5416: 5409:Insertion Sort 5405: 5402: 5399: 5394: 5379: 5375: 5362: 5347: 5343: 5330: 5315: 5311: 5298: 5294: 5293: 5287: 5284: 5281: 5276: 5262: 5259: 5256: 5253: 5242: 5228: 5225: 5222: 5219: 5208: 5194: 5191: 5188: 5185: 5174: 5168: 5167: 5149: 5146: 5143: 5140: 5116: 5113: 5110: 5107: 5094: 5091: 5088: 5074: 5070: 5058: 5051: 5044: 5037: 5031: 5030: 5027: 5024: 5021: 5018: 5015: 5012: 5009: 4983: 4980: 4970: 4969: 4966: 4963: 4960: 4947: 4943: 4939: 4936: 4926: 4913: 4910: 4905: 4902: 4892: 4879: 4876: 4871: 4868: 4858: 4855: 4849: 4848: 4844: 4841: 4838: 4833: 4820: 4816: 4805: 4794: 4791: 4788: 4778: 4773: 4767: 4766: 4763: 4760: 4757: 4744: 4741: 4736: 4733: 4723: 4710: 4707: 4702: 4699: 4689: 4676: 4673: 4668: 4665: 4655: 4652: 4646: 4645: 4635: 4632: 4629: 4616: 4612: 4608: 4603: 4600: 4588: 4576: 4572: 4569: 4564: 4561: 4555: 4551: 4548: 4538: 4525: 4522: 4517: 4514: 4504: 4499: 4493: 4492: 4480: 4476: 4472: 4461: 4458: 4455: 4442: 4438: 4427: 4414: 4411: 4406: 4403: 4393: 4380: 4377: 4372: 4369: 4359: 4356: 4353:MSD Radix Sort 4349: 4348: 4338: 4335: 4332: 4319: 4315: 4311: 4308: 4298: 4285: 4282: 4277: 4274: 4264: 4251: 4248: 4243: 4240: 4230: 4227: 4225:MSD Radix Sort 4221: 4220: 4203: 4200: 4188: 4185: 4182: 4169: 4165: 4161: 4158: 4148: 4135: 4132: 4127: 4124: 4114: 4101: 4098: 4093: 4090: 4080: 4069: 4059: 4057:LSD Radix Sort 4053: 4052: 4038: 4035: 4032: 4029: 4005: 4002: 3999: 3996: 3979: 3976: 3973: 3962: 3959: 3956: 3946: 3935: 3932: 3929: 3919: 3908: 3905: 3902: 3892: 3889: 3883: 3882: 3868: 3865: 3862: 3859: 3835: 3832: 3829: 3826: 3809: 3806: 3803: 3792: 3789: 3786: 3776: 3765: 3762: 3759: 3749: 3738: 3735: 3732: 3722: 3719: 3712: 3711: 3705: 3702: 3699: 3688: 3685: 3682: 3672: 3661: 3658: 3653: 3649: 3638: 3627: 3624: 3621: 3611: 3608: 3601: 3600: 3597: 3594: 3591: 3578: 3574: 3563: 3550: 3546: 3542: 3539: 3529: 3516: 3512: 3508: 3505: 3495: 3492: 3486: 3485: 3482: 3474: 3471: 3468: 3465: 3462: 3459: 3450: 3449: 3447: 3426: 3423: 3418: 3408: 3389: 3370: 3367: 3362: 3359: 3349: 3348: 3341: 3331: 3280: 3277: 3274: 3273: 3270: 3267: 3264: 3259: 3245: 3241: 3229: 3215: 3211: 3199: 3185: 3181: 3169: 3163: 3162: 3159: 3156: 3153: 3148: 3134: 3130: 3118: 3104: 3100: 3088: 3074: 3070: 3058: 3052: 3051: 3037: 3034: 3031: 3028: 3015: 3012: 3009: 3004: 2990: 2986: 2974: 2960: 2956: 2944: 2930: 2926: 2914: 2912:Selection sort 2908: 2907: 2905: 2902: 2899: 2892: 2878: 2874: 2862: 2848: 2844: 2832: 2825: 2819: 2818: 2815: 2812: 2809: 2804: 2790: 2786: 2774: 2760: 2756: 2744: 2737: 2731: 2730: 2727: 2724: 2721: 2716: 2702: 2698: 2686: 2672: 2668: 2656: 2649: 2643: 2642: 2639: 2636: 2633: 2628: 2614: 2610: 2598: 2584: 2580: 2568: 2561: 2555: 2554: 2551: 2548: 2545: 2540: 2526: 2522: 2510: 2496: 2492: 2480: 2473: 2467: 2466: 2463: 2460: 2457: 2452: 2438: 2434: 2422: 2408: 2404: 2392: 2385: 2379: 2378: 2354: 2351: 2348: 2343: 2329: 2325: 2313: 2299: 2295: 2283: 2276: 2274:Insertion sort 2270: 2269: 2266: 2263: 2260: 2255: 2241: 2237: 2225: 2211: 2207: 2195: 2183: 2180: 2177: 2174: 2163: 2157: 2156: 2153: 2150: 2147: 2142: 2128: 2124: 2120: 2116: 2104: 2090: 2086: 2082: 2078: 2066: 2054: 2051: 2048: 2045: 2034: 2028: 2027: 2024: 2021: 2018: 2011: 1997: 1993: 1981: 1969: 1966: 1963: 1960: 1949: 1937: 1934: 1931: 1928: 1917: 1911: 1910: 1896: 1893: 1890: 1878: 1875: 1872: 1861: 1847: 1843: 1831: 1819: 1816: 1813: 1810: 1799: 1787: 1784: 1781: 1778: 1767: 1761: 1760: 1753: 1750: 1747: 1740: 1728: 1725: 1722: 1719: 1708: 1696: 1693: 1690: 1687: 1676: 1669: 1663: 1662: 1642:Finds all the 1640: 1637: 1634: 1627: 1615: 1612: 1609: 1606: 1595: 1583: 1580: 1577: 1574: 1563: 1556: 1550: 1549: 1542: 1539: 1536: 1529: 1517: 1514: 1511: 1508: 1497: 1485: 1482: 1479: 1476: 1465: 1458: 1452: 1451: 1436: 1433: 1430: 1425: 1413: 1410: 1407: 1404: 1393: 1381: 1378: 1375: 1372: 1361: 1354: 1348: 1347: 1329: 1326: 1323: 1320: 1307: 1304: 1301: 1296: 1284: 1281: 1278: 1275: 1264: 1252: 1249: 1246: 1243: 1232: 1225: 1219: 1218: 1211: 1208: 1205: 1198: 1184: 1181: 1178: 1175: 1164: 1152: 1149: 1146: 1143: 1132: 1120: 1117: 1114: 1111: 1100: 1094: 1093: 1090: 1087: 1084: 1077: 1065: 1062: 1059: 1056: 1045: 1033: 1030: 1027: 1024: 1013: 1001: 998: 995: 992: 981: 975: 974: 957: 954: 951: 944: 932: 929: 926: 923: 912: 900: 897: 894: 891: 880: 868: 865: 862: 859: 848: 842: 841: 834: 831: 828: 816: 813: 810: 799: 787: 784: 781: 778: 767: 755: 752: 749: 746: 735: 723: 720: 717: 714: 703: 697: 696: 694: 691: 688: 683: 671: 668: 665: 662: 651: 639: 636: 633: 630: 619: 607: 604: 601: 598: 587: 581: 580: 577: 574: 571: 566: 554: 551: 546: 542: 538: 527: 524: 521: 515: 514: 511: 508: 505: 502: 499: 496: 493: 455: 452: 451: 450: 432: 429:big O notation 425: 422: 415: 401: 398: 335: 332: 331: 330: 327: 320: 317: 310: 303: 296: 293: 279: 278: 277: 274: 234: 233:Classification 231: 191:big O notation 127: 124: 112:data structure 108: 107: 100: 86:canonicalizing 26: 9: 6: 4: 3: 2: 9752: 9741: 9738: 9736: 9733: 9732: 9730: 9715: 9712: 9710: 9707: 9705: 9702: 9701: 9699: 9695: 9689: 9686: 9684: 9681: 9677: 9674: 9673: 9672: 9669: 9668: 9666: 9662: 9656: 9653: 9651: 9648: 9646: 9643: 9641: 9638: 9636: 9633: 9631: 9628: 9627: 9625: 9623: 9619: 9613: 9610: 9608: 9605: 9603: 9600: 9598: 9595: 9594: 9592: 9588: 9582: 9579: 9577: 9574: 9572: 9569: 9567: 9564: 9562: 9559: 9557: 9556:Counting sort 9554: 9552: 9549: 9547: 9544: 9542: 9539: 9537: 9534: 9533: 9531: 9527: 9521: 9518: 9516: 9513: 9511: 9508: 9506: 9503: 9502: 9500: 9496: 9490: 9487: 9485: 9482: 9480: 9477: 9475: 9472: 9470: 9467: 9465: 9462: 9461: 9459: 9455: 9449: 9446: 9444: 9441: 9439: 9436: 9434: 9431: 9429: 9426: 9424: 9421: 9419: 9416: 9415: 9413: 9411: 9407: 9401: 9398: 9396: 9393: 9391: 9388: 9386: 9383: 9381: 9380:Odd–even sort 9378: 9376: 9373: 9371: 9368: 9367: 9365: 9361: 9355: 9352: 9350: 9347: 9345: 9344:X + Y sorting 9342: 9340: 9337: 9335: 9332: 9330: 9329:Adaptive sort 9327: 9325: 9322: 9320: 9317: 9315: 9312: 9310: 9307: 9305: 9302: 9300: 9297: 9295: 9292: 9291: 9289: 9285: 9281: 9274: 9269: 9267: 9262: 9260: 9255: 9254: 9251: 9239: 9236: 9234: 9231: 9230: 9227: 9221: 9218: 9216: 9213: 9211: 9208: 9206: 9203: 9201: 9198: 9196: 9193: 9191: 9188: 9186: 9183: 9181: 9178: 9176: 9173: 9171: 9170:Hash function 9168: 9166: 9163: 9161: 9158: 9156: 9153: 9151: 9148: 9146: 9143: 9141: 9138: 9136: 9133: 9131: 9128: 9126: 9125:Binary search 9123: 9121: 9118: 9117: 9115: 9111: 9105: 9102: 9100: 9097: 9095: 9092: 9090: 9087: 9085: 9082: 9080: 9077: 9075: 9072: 9070: 9067: 9065: 9062: 9060: 9057: 9055: 9052: 9050: 9047: 9045: 9042: 9040: 9037: 9036: 9034: 9030: 9026: 9022: 9015: 9010: 9008: 9003: 9001: 8996: 8995: 8992: 8985: 8981: 8978: 8975: 8972: 8969: 8965: 8962: 8959: 8956: 8953: 8949: 8946: 8943: 8940: 8937: 8934: 8931: 8927: 8924: 8923: 8914: 8912:0-12-394680-8 8908: 8904: 8900: 8896: 8892: 8888: 8885: 8883:0-201-89685-0 8879: 8875: 8871: 8867: 8866: 8855: 8854:0-7167-8042-9 8851: 8847: 8843: 8839: 8834: 8827: 8826:0-201-89685-0 8823: 8819: 8815: 8814: 8809: 8804: 8788: 8784: 8780: 8774: 8759: 8755: 8751: 8745: 8730: 8726: 8722: 8716: 8708: 8704: 8700: 8697: 8696: 8688: 8673: 8669: 8668: 8663: 8657: 8650: 8645: 8631:on 2017-08-30 8627: 8623: 8619: 8615: 8611: 8607: 8603: 8596: 8589: 8582: 8578: 8574: 8570: 8563: 8556: 8550: 8546: 8542: 8538: 8534: 8530: 8524: 8517: 8512: 8505: 8500: 8494: 8490: 8486: 8481: 8465: 8461: 8457: 8451: 8435: 8431: 8427: 8421: 8405: 8401: 8397: 8391: 8384: 8379: 8372: 8367: 8359: 8353: 8349: 8345: 8339: 8331: 8327: 8323: 8319: 8315: 8311: 8307: 8300: 8292: 8290:0-7695-1822-2 8286: 8282: 8278: 8274: 8270: 8266: 8259: 8251: 8247: 8243: 8239: 8235: 8231: 8227: 8221: 8213: 8209: 8205: 8201: 8194: 8176: 8172: 8166: 8162: 8158: 8151: 8150: 8142: 8133: 8128: 8121: 8113: 8107: 8103: 8099: 8095: 8089: 8087: 8078: 8076:0-262-03293-7 8072: 8068: 8067: 8062: 8058: 8054: 8050: 8044: 8042: 8040: 8024: 8020: 8019: 8014: 8007: 8000: 7998:0-262-03293-7 7994: 7990: 7989: 7985:(2001), "8", 7984: 7980: 7976: 7972: 7966: 7950: 7946: 7942: 7936: 7928: 7924: 7920: 7916: 7912: 7908: 7907: 7902: 7901:Sedgewick, R. 7896: 7881: 7875: 7871: 7870: 7865: 7859: 7851: 7845: 7841: 7837: 7832: 7827: 7823: 7819: 7815: 7811: 7804: 7785: 7781: 7774: 7767: 7759: 7757:0-89791-099-0 7753: 7749: 7745: 7741: 7737: 7733: 7725: 7724:Szemerédi, E. 7721: 7717: 7711: 7703: 7699: 7694: 7689: 7685: 7682: 7681: 7673: 7666: 7660: 7656: 7655: 7651:(2009), "8", 7650: 7646: 7642: 7638: 7632: 7624: 7620: 7616: 7609: 7593: 7589: 7582: 7567: 7563: 7559: 7553: 7549: 7539: 7536: 7533: 7530: 7527: 7524: 7522: 7519: 7516: 7513: 7512: 7506: 7504: 7500: 7496: 7492: 7488: 7484: 7479: 7477: 7473: 7468: 7466: 7462: 7458: 7454: 7450: 7446: 7442: 7438: 7434: 7430: 7426: 7416: 7414: 7408: 7406: 7402: 7398: 7394: 7389: 7387: 7382: 7379: 7374: 7372: 7368: 7357: 7355: 7351: 7347: 7346:counting sort 7343: 7339: 7335: 7331: 7327: 7323: 7319: 7314: 7304: 7301: 7299: 7298:counting sort 7295: 7289: 7279: 7277: 7273: 7268: 7265:th member of 7264: 7260: 7256: 7252: 7248: 7244: 7240: 7236: 7230: 7229:Counting sort 7223:Counting sort 7220: 7218: 7214: 7210: 7206: 7202: 7197: 7187: 7185: 7181: 7176: 7175:Exchange sort 7170:Exchange sort 7167: 7165: 7161: 7157: 7155: 7150: 7146: 7141: 7131: 7129: 7127: 7123: 7118: 7113: 7105: 7100: 7091: 7089: 7088:cocktail sort 7085: 7075: 7073: 7069: 7065: 7061: 7057: 7053: 7049: 7045: 7041: 7037: 7033: 7028: 7026: 7022: 7001: 6998: 6992: 6982: 6978: 6973: 6965: 6960: 6951: 6949: 6948:ordered array 6927: 6921: 6916: 6912: 6905: 6902: 6899: 6891: 6887: 6882: 6880: 6876: 6872: 6868: 6865: 6861: 6857: 6853: 6849: 6845: 6841: 6837: 6832: 6830: 6826: 6822: 6818: 6814: 6810: 6806: 6802: 6797: 6787: 6785: 6781: 6777: 6773: 6769: 6765: 6761: 6757: 6752: 6742: 6740: 6736: 6732: 6728: 6724: 6720: 6715: 6713: 6709: 6705: 6700: 6695: 6685: 6683: 6679: 6675: 6671: 6665: 6663: 6659: 6655: 6651: 6641: 6639: 6634: 6632: 6628: 6624: 6620: 6617: 6613: 6608: 6598: 6596: 6591: 6590: 6584: 6574: 6565: 6563: 6558: 6552: 6550: 6545: 6543: 6539: 6535: 6531: 6527: 6523: 6519: 6515: 6501: 6497: 6480: 6474: 6471: 6468: 6465: 6462: 6456: 6452: 6449: 6446: 6443: 6439: 6435: 6427: 6423: 6406: 6400: 6397: 6394: 6389: 6385: 6381: 6373: 6370: 6366: 6349: 6343: 6340: 6337: 6334: 6331: 6326: 6322: 6318: 6310: 6307:A randomized 6306: 6303: 6299: 6293: 6289: 6285: 6280: 6277: 6276: 6275: 6273: 6269: 6265: 6253: 6249: 6241: 6238: 6233: 6218: 6215: 6212: 6209: 6201: 6186: 6183: 6180: 6177: 6169: 6154: 6146: 6143: 6138: 6131: 6128: 6121: 6101: 6098: 6095: 6085: 6076: 6056: 6053: 6050: 6040: 6031: 6011: 6008: 6005: 5995: 5986: 5984: 5981: 5976: 5970: 5966: 5962: 5958: 5950: 5947: 5940: 5923: 5920: 5917: 5913: 5909: 5906: 5903: 5899: 5890: 5873: 5870: 5867: 5863: 5859: 5856: 5853: 5849: 5840: 5823: 5820: 5817: 5813: 5809: 5806: 5803: 5799: 5790: 5788: 5785: 5781: 5764: 5761: 5758: 5755: 5749: 5736: 5733: 5728: 5723: 5705: 5702: 5699: 5696: 5685: 5678: 5676: 5673: 5665: 5662: 5657: 5641: 5638: 5633: 5629: 5625: 5617: 5601: 5598: 5593: 5589: 5580: 5564: 5561: 5556: 5552: 5543: 5541: 5538: 5530: 5522: 5517: 5512: 5507: 5505: 5502: 5497: 5493: 5489: 5485: 5478: 5475: 5458: 5454: 5445: 5438: 5431: 5424: 5422: 5419: 5414: 5413:Exchange Sort 5410: 5403: 5400: 5395: 5377: 5373: 5363: 5345: 5341: 5331: 5313: 5309: 5299: 5296: 5292: 5285: 5282: 5277: 5260: 5257: 5254: 5251: 5243: 5226: 5223: 5220: 5217: 5209: 5192: 5189: 5186: 5183: 5175: 5173: 5170: 5144: 5138: 5111: 5105: 5092: 5072: 5068: 5059: 5052: 5045: 5038: 5036: 5033: 5028: 5025: 5022: 5019: 5016: 5013: 5010: 5007: 5006: 5003: 5001: 4997: 4993: 4989: 4979: 4976: 4964: 4961: 4945: 4941: 4937: 4934: 4927: 4911: 4908: 4903: 4900: 4893: 4877: 4874: 4869: 4866: 4859: 4856: 4854: 4851: 4842: 4839: 4834: 4818: 4814: 4806: 4792: 4789: 4786: 4779: 4774: 4772: 4769: 4761: 4758: 4742: 4739: 4734: 4731: 4724: 4708: 4705: 4700: 4697: 4690: 4674: 4671: 4666: 4663: 4656: 4653: 4651: 4648: 4641: 4633: 4630: 4614: 4610: 4606: 4601: 4598: 4589: 4574: 4570: 4567: 4562: 4559: 4553: 4549: 4546: 4539: 4523: 4520: 4515: 4512: 4505: 4500: 4498: 4495: 4478: 4474: 4470: 4459: 4456: 4440: 4436: 4428: 4412: 4409: 4404: 4401: 4394: 4378: 4375: 4370: 4367: 4360: 4357: 4354: 4351: 4347: 4336: 4333: 4317: 4313: 4309: 4306: 4299: 4283: 4280: 4275: 4272: 4265: 4249: 4246: 4241: 4238: 4231: 4228: 4226: 4223: 4219: 4201: 4198: 4186: 4183: 4167: 4163: 4159: 4156: 4149: 4133: 4130: 4125: 4122: 4115: 4099: 4096: 4091: 4088: 4081: 4067: 4060: 4058: 4055: 4033: 4027: 4000: 3994: 3984: 3977: 3974: 3960: 3957: 3954: 3947: 3933: 3930: 3927: 3920: 3906: 3903: 3900: 3893: 3890: 3888: 3887:Counting sort 3885: 3863: 3857: 3830: 3824: 3814: 3807: 3804: 3790: 3787: 3784: 3777: 3763: 3760: 3757: 3750: 3736: 3733: 3730: 3723: 3720: 3717: 3714: 3710: 3703: 3700: 3686: 3683: 3680: 3673: 3659: 3656: 3651: 3647: 3639: 3625: 3622: 3619: 3612: 3609: 3606: 3603: 3595: 3592: 3576: 3572: 3564: 3548: 3544: 3540: 3537: 3530: 3514: 3510: 3506: 3503: 3496: 3493: 3491: 3488: 3483: 3479: 3475: 3472: 3469: 3466: 3463: 3460: 3457: 3456: 3448: 3424: 3421: 3416: 3398: 3394: 3368: 3365: 3360: 3357: 3346: 3342: 3337: 3332: 3322:, digit size 3313: 3312: 3311: 3309: 3305: 3303: 3299: 3295: 3290: 3286: 3268: 3265: 3260: 3243: 3239: 3230: 3213: 3209: 3200: 3183: 3179: 3170: 3168: 3165: 3157: 3154: 3149: 3132: 3128: 3119: 3102: 3098: 3089: 3072: 3068: 3059: 3057: 3056:Exchange sort 3054: 3032: 3026: 3013: 3010: 3005: 2988: 2984: 2975: 2958: 2954: 2945: 2928: 2924: 2915: 2913: 2910: 2903: 2900: 2893: 2876: 2872: 2863: 2846: 2842: 2833: 2826: 2824: 2821: 2813: 2810: 2805: 2788: 2784: 2775: 2758: 2754: 2745: 2738: 2736: 2733: 2725: 2722: 2717: 2700: 2696: 2687: 2670: 2666: 2657: 2650: 2648: 2647:Odd–even sort 2645: 2637: 2634: 2629: 2612: 2608: 2599: 2582: 2578: 2569: 2562: 2560: 2557: 2549: 2546: 2541: 2524: 2520: 2511: 2494: 2490: 2481: 2474: 2472: 2469: 2461: 2458: 2453: 2436: 2432: 2423: 2406: 2402: 2393: 2386: 2384: 2381: 2376: 2373: 2367: 2363: 2359: 2352: 2349: 2344: 2327: 2323: 2314: 2297: 2293: 2284: 2277: 2275: 2272: 2264: 2261: 2256: 2239: 2235: 2226: 2209: 2205: 2196: 2181: 2178: 2175: 2172: 2164: 2162: 2159: 2151: 2148: 2143: 2126: 2122: 2118: 2114: 2105: 2088: 2084: 2080: 2076: 2067: 2052: 2049: 2046: 2043: 2035: 2033: 2030: 2022: 2019: 2012: 1995: 1991: 1982: 1967: 1964: 1961: 1958: 1950: 1935: 1932: 1929: 1926: 1918: 1916: 1913: 1909:stack space. 1906: 1902: 1895:Partitioning 1894: 1891: 1876: 1873: 1870: 1862: 1845: 1841: 1832: 1817: 1814: 1811: 1808: 1800: 1785: 1782: 1779: 1776: 1768: 1766: 1763: 1758: 1751: 1748: 1741: 1726: 1723: 1720: 1717: 1709: 1694: 1691: 1688: 1685: 1677: 1670: 1668: 1665: 1658: 1654: 1650: 1645: 1638: 1635: 1628: 1613: 1610: 1607: 1604: 1596: 1581: 1578: 1575: 1572: 1564: 1557: 1555: 1552: 1547: 1540: 1537: 1530: 1515: 1512: 1509: 1506: 1498: 1483: 1480: 1477: 1474: 1466: 1459: 1457: 1454: 1449: 1445: 1441: 1434: 1431: 1426: 1411: 1408: 1405: 1402: 1394: 1379: 1376: 1373: 1370: 1362: 1355: 1353: 1350: 1345: 1324: 1318: 1305: 1302: 1297: 1282: 1279: 1276: 1273: 1265: 1250: 1247: 1244: 1241: 1233: 1226: 1224: 1221: 1216: 1213:When using a 1209: 1206: 1199: 1182: 1179: 1176: 1173: 1165: 1150: 1147: 1144: 1141: 1133: 1118: 1115: 1112: 1109: 1101: 1099: 1096: 1088: 1085: 1078: 1063: 1060: 1057: 1054: 1046: 1031: 1028: 1025: 1022: 1014: 999: 996: 993: 990: 982: 980: 977: 970: 966: 961: 955: 952: 945: 930: 927: 924: 921: 913: 898: 895: 892: 889: 881: 866: 863: 860: 857: 849: 847: 844: 839: 832: 829: 814: 811: 808: 800: 785: 782: 779: 776: 768: 753: 750: 747: 744: 736: 721: 718: 715: 712: 704: 702: 699: 692: 689: 684: 669: 666: 663: 660: 652: 637: 634: 631: 628: 620: 605: 602: 599: 596: 588: 586: 583: 575: 572: 567: 552: 549: 544: 540: 536: 528: 525: 522: 520: 512: 509: 506: 503: 500: 497: 494: 491: 490: 487: 482: 478: 474: 470: 465: 461: 446: 439: 434:The notation 433: 430: 426: 423: 420: 416: 410: 409: 408: 405: 397: 395: 390: 388: 383: 371: 367: 363: 361: 356: 354: 349: 340: 328: 325: 321: 318: 315: 311: 308: 304: 301: 297: 294: 291: 287: 283: 280: 275: 272: 268: 264: 260: 256: 252: 248: 245: 244: 243: 240: 239: 238: 230: 226: 224: 220: 216: 212: 208: 204: 200: 196: 192: 188: 183: 181: 180:counting sort 177: 173: 169: 167: 163: 156: 154: 150: 146: 142: 138: 134: 123: 121: 117: 116:random access 114:which allows 113: 105: 101: 98: 94: 93: 92: 89: 87: 83: 79: 75: 71: 67: 63: 59: 55: 51: 47: 43: 36: 32: 19: 9622:Hybrid sorts 9571:Proxmap sort 9484:Library sort 9354:Quantum sort 9279: 9199: 9195:Root-finding 9120:Backtracking 9084:Segment tree 9054:Fenwick tree 8984:Google Colab 8898: 8873: 8845: 8842:Sartaj Sahni 8833: 8817: 8816:, Volume 3: 8811: 8808:Donald Knuth 8803: 8791:. Retrieved 8782: 8773: 8762:. Retrieved 8753: 8744: 8733:. Retrieved 8724: 8715: 8698: 8693: 8687: 8676:. Retrieved 8665: 8656: 8644: 8633:. Retrieved 8626:the original 8608:(7): 30–32. 8605: 8601: 8588: 8572: 8568: 8562: 8544: 8523: 8518:, p. 93 8511: 8499: 8480: 8468:. Retrieved 8459: 8450: 8438:. Retrieved 8434:the original 8429: 8420: 8408:. Retrieved 8399: 8390: 8378: 8366: 8347: 8338: 8313: 8310:Algorithmica 8309: 8299: 8268: 8263:Han, Yijie; 8258: 8233: 8229: 8220: 8203: 8199: 8193: 8182:, retrieved 8148: 8141: 8120: 8101: 8065: 8027:. Retrieved 8016: 8006: 7987: 7965: 7953:. Retrieved 7945:Algolist.net 7944: 7935: 7910: 7904: 7895: 7883:. Retrieved 7868: 7858: 7817: 7809: 7803: 7791:. Retrieved 7779: 7766: 7739: 7727: 7710: 7683: 7678: 7672: 7653: 7631: 7614: 7608: 7596:. Retrieved 7581: 7570:. Retrieved 7562:Mental Floss 7561: 7552: 7538:Quantum sort 7494: 7480: 7469: 7448: 7440: 7436: 7422: 7409: 7400: 7390: 7383: 7375: 7363: 7333: 7329: 7325: 7321: 7317: 7316: 7302: 7291: 7275: 7271: 7266: 7262: 7258: 7254: 7250: 7246: 7242: 7238: 7234: 7232: 7200: 7199: 7179: 7174: 7173: 7163: 7159: 7153: 7144: 7143: 7130: 7125: 7121: 7116: 7115: 7081: 7055: 7051: 7047: 7043: 7039: 7035: 7032:open problem 7029: 7024: 7020: 6981:Donald Shell 6976: 6975: 6889: 6885: 6883: 6878: 6874: 6870: 6859: 6855: 6847: 6843: 6839: 6835: 6833: 6828: 6824: 6820: 6812: 6808: 6800: 6799: 6783: 6779: 6775: 6771: 6755: 6754: 6716: 6711: 6707: 6703: 6698: 6697: 6669: 6666: 6661: 6657: 6653: 6649: 6647: 6637: 6635: 6626: 6611: 6610: 6587: 6586: 6571: 6568:Simple sorts 6562:library sort 6553: 6546: 6510: 6499: 6495: 6425: 6421: 6368: 6364: 6301: 6297: 6291: 6287: 6283: 6278: 6271: 6267: 6263: 6261: 6251: 6247: 5968: 5964: 5960: 5956: 5780:worst case. 5741: 5654:non-parallel 5491: 5487: 5483: 5290: 5029:Other notes 4999: 4995: 4985: 4973: 4853:Postman sort 4639: 4345: 4217: 3982: 3812: 3708: 3477: 3396: 3392: 3335: 3301: 3297: 3293: 3282: 3017:Stable with 2371: 2365: 2361: 2357: 1915:Library sort 1904: 1900: 1756: 1656: 1652: 1648: 1545: 968: 964: 513:Other notes 481:on average. 476: 472: 468: 457: 444: 437: 406: 403: 391: 384: 372: 368: 364: 359: 357: 350: 346: 313: 289: 270: 266: 262: 258: 254: 250: 236: 227: 207:binary trees 184: 175: 171: 165: 161: 157: 153:library sort 129: 109: 90: 45: 39: 9704:Stooge sort 9546:Bucket sort 9498:Merge sorts 9370:Bubble sort 9314:Inplacement 9304:Total order 9074:Linked list 7885:27 November 7598:16 December 7590:. NYTimes. 7453:quickselect 7288:Bucket sort 7282:Bucket sort 7205:bucket sort 7149:bubble sort 7117:Bubble sort 7112:Bubble sort 7094:Bubble sort 6768:binary tree 5787:Stooge sort 5274:comparisons 5240:comparisons 5206:comparisons 4992:stooge sort 4355:(in-place) 3716:Bucket sort 3605:Bucket sort 3158:Exchanging 2823:Strand sort 2726:Exchanging 2638:Exchanging 2550:Exchanging 2462:Exchanging 2383:Bubble sort 2265:Exchanging 1448:binary heap 378:), hearts ( 298:Stability: 145:Bubble sort 104:permutation 9729:Categories 9650:Spreadsort 9612:Samplesort 9576:Radix sort 9505:Merge sort 9443:Cycle sort 9428:Smoothsort 9390:Gnome sort 9210:Sweep line 9185:Randomized 9113:Algorithms 9064:Hash table 9025:algorithms 8954:algorithm. 8764:2021-07-10 8735:2021-07-10 8678:2012-05-05 8649:Wirth 1986 8635:2020-03-23 8516:Wirth 1986 8504:Wirth 1986 8400:python.org 8383:Wirth 1986 8371:Wirth 1986 8265:Thorup, M. 8226:Thorup, M. 8184:2020-06-27 8132:2110.01111 8029:2015-11-23 8018:Dr. Dobb's 7730:O(n log n) 7720:Komlós, J. 7680:Comput. J. 7572:2016-06-16 7545:References 7405:merge sort 7367:system bus 7318:Radix sort 7313:Radix sort 7307:Radix sort 7194:See also: 7064:call stack 6699:Merge sort 6694:Merge sort 6688:Merge sort 5026:Comparison 4994:which has 4975:Samplesort 4497:Spreadsort 3403:, because 3269:Selection 3167:Cycle sort 3014:Selection 2904:Selection 2814:Selection 2559:Gnome sort 2375:inversions 2353:Insertion 2152:Insertion 2023:Insertion 1752:Insertion 1435:Selection 1352:Smoothsort 1223:Block sort 1210:Insertion 1196:(balanced) 1089:Selection 846:Merge sort 693:Selection 394:radix sort 217:analysis, 74:efficiency 35:Merge sort 9645:Introsort 9581:Flashsort 9551:Burstsort 9541:Bead sort 9479:Tree sort 9474:Splaysort 9469:Shellsort 9400:Quicksort 9385:Comb sort 9319:Stability 9205:Streaming 9190:Recursion 8952:quicksort 8783:Pcmag.com 8330:1432-0541 8063:(2001) . 7906:Comm. ACM 7826:CiteSeerX 7716:Ajtai, M. 7688:CiteSeerX 7623:301940891 7515:Collation 7457:quicksort 7445:selection 7397:quicksort 7378:quicksort 7209:flashsort 7145:Comb sort 7140:Comb sort 7134:Comb sort 7084:Comb sort 6977:Shellsort 6972:Shellsort 6954:Shellsort 6934:⌋ 6922:⁡ 6909:⌊ 6809:partition 6801:Quicksort 6796:Quicksort 6790:Quicksort 6682:introsort 6621:. It has 6595:Shellsort 6534:introsort 6494:time and 6472:⁡ 6466:⁡ 6450:⁡ 6420:time and 6398:⁡ 6341:⁡ 6335:⁡ 6296:time and 6216:⁡ 6184:⁡ 6155:− 6099:⁡ 6090:Ω 6054:⁡ 6045:Ω 6009:⁡ 6000:Ω 5921:⁡ 5907:⁡ 5871:⁡ 5857:⁡ 5821:⁡ 5807:⁡ 5759:× 5725:Unbounded 5700:× 5639:⁡ 5599:⁡ 5562:⁡ 5258:⁡ 5224:⁡ 5190:⁡ 5035:Bead sort 4904:⋅ 4870:⋅ 4771:Flashsort 4735:⋅ 4701:⋅ 4667:⋅ 4650:Burstsort 4607:⋅ 4550:⋅ 4516:⋅ 4405:⋅ 4371:⋅ 4276:⋅ 4242:⋅ 4126:⋅ 4092:⋅ 3684:⋅ 3657:⋅ 3361:⋅ 2179:⁡ 2161:Comb sort 2050:⁡ 2032:Shellsort 1965:⁡ 1933:⁡ 1874:⁡ 1815:⁡ 1783:⁡ 1765:Quicksort 1724:⁡ 1692:⁡ 1611:⁡ 1579:⁡ 1513:⁡ 1481:⁡ 1409:⁡ 1377:⁡ 1280:⁡ 1248:⁡ 1180:⁡ 1148:⁡ 1116:⁡ 1098:Tree sort 1061:⁡ 1029:⁡ 997:⁡ 928:⁡ 896:⁡ 864:⁡ 812:⁡ 783:⁡ 751:⁡ 719:⁡ 701:Introsort 667:⁡ 635:⁡ 603:⁡ 550:⁡ 334:Stability 97:monotonic 50:algorithm 9714:Bogosort 9709:Slowsort 9423:Heapsort 8893:(1980), 8872:(1998), 8793:14 April 8787:Archived 8758:Archived 8729:Archived 8672:Archived 8622:28572656 8543:(2009), 8489:Archived 8470:14 April 8464:Archived 8440:14 April 8430:java.net 8410:14 April 8404:Archived 8346:(1986). 8267:(2002). 8175:archived 8023:Archived 7955:14 April 7949:Archived 7927:10020756 7784:Archived 7726:(1983). 7619:ProQuest 7592:Archived 7566:Archived 7509:See also 7156:Magazine 7104:swapping 7060:in-place 7050:) and Θ( 6817:in-place 6756:Heapsort 6751:Heapsort 6745:Heapsort 6674:unstable 6616:in-place 6538:C++ sort 6502:) space. 6371:) space. 6304:) space. 6290:log log 5983:Slowsort 5675:Bogosort 5614:parallel 5577:parallel 5479:Polling 5162:, where 4988:bogosort 1667:Cubesort 1440:adaptive 956:Merging 585:Heapsort 576:Merging 407:Legend: 353:data set 324:adaptive 286:in-place 201:such as 56:into an 9640:Timsort 9200:Sorting 9175:Minimax 8928:at the 8903:101–130 8487:, Sun. 8250:9700543 7793:1 March 7495:ranking 7164:Rabbits 7160:turtles 7017:⁠ 6985:⁠ 6729:(as of 6719:Timsort 6678:Timsort 6522:Android 6518:Timsort 5160:⁠ 5131:⁠ 5127:⁠ 5098:⁠ 5014:Average 4049:⁠ 4020:⁠ 4016:⁠ 3987:⁠ 3879:⁠ 3850:⁠ 3846:⁠ 3817:⁠ 3464:Average 3048:⁠ 3019:⁠ 1456:Timsort 1340:⁠ 1311:⁠ 962:(up to 498:Average 343:output. 149:Timsort 70:sorting 9287:Theory 9180:Online 9165:Greedy 9094:String 8909: 8880: 8852: 8824: 8667:GitHub 8620: 8551: 8354: 8328: 8287: 8248: 8167: 8108: 8073: 7995: 7925: 7876: 7846: 7828: 7816:2008. 7754: 7690: 7661: 7621: 7487:sports 7429:amount 7350:hybrid 7128:time. 6852:median 6739:JDK1.3 6723:Python 6614:is an 6532:, and 6530:Python 6528:, and 6245:Makes 5524:Varies 5519:Varies 5514:Varies 5509:Varies 5279:Varies 5023:Stable 5020:Memory 4982:Others 3484:Notes 3473:Stable 3470:Memory 3326:, and 1755:Makes 1544:Makes 510:Method 507:Stable 504:Memory 441:means 282:Memory 221:, and 141:UNIVAC 78:search 48:is an 9664:Other 9309:Lists 9089:Stack 9079:Queue 9059:Graph 9039:Array 8629:(PDF) 8618:S2CID 8598:(PDF) 8246:S2CID 8178:(PDF) 8153:(PDF) 8127:arXiv 7923:S2CID 7787:(PDF) 7776:(PDF) 7738:'83. 7042:) to 6813:pivot 6803:is a 5017:Worst 3467:Worst 1903:(log 967:(log 501:Worst 443:(log 203:heaps 137:ENIAC 82:merge 58:order 9160:Fold 9104:Trie 9099:Tree 9069:Heap 9023:and 8907:ISBN 8878:ISBN 8850:ISBN 8840:and 8822:ISBN 8795:2018 8549:ISBN 8472:2018 8442:2018 8412:2018 8352:ISBN 8326:ISSN 8285:ISBN 8165:ISBN 8106:ISBN 8071:ISBN 7993:ISBN 7957:2018 7887:2012 7874:ISBN 7844:ISBN 7822:LNCS 7814:TAMC 7795:2022 7752:ISBN 7736:STOC 7659:ISBN 7600:2014 7241:| + 7207:and 7154:Byte 7086:and 7070:and 7054:log 6888:log 6846:log 6823:log 6782:log 6764:heap 6735:Perl 6731:JDK7 6727:Java 6725:and 6706:log 6652:log 6542:.NET 6526:Java 6270:log 6242:Yes 6239:Yes 6132:Yes 5963:) = 5951:Yes 5737:Yes 5666:Yes 5531:Yes 5476:Yes 5404:Yes 5286:Yes 5011:Best 5008:Name 4334:Yes 4184:Yes 3978:Yes 3975:Yes 3808:Yes 3805:Yes 3701:Yes 3596:Yes 3593:Yes 3461:Best 3458:Name 3395:log 3300:log 2901:Yes 2723:Yes 2635:Yes 2547:Yes 2459:Yes 2350:Yes 1749:Yes 1655:log 1538:Yes 1303:Yes 1207:Yes 953:Yes 573:Yes 495:Best 492:Name 475:log 436:log 314:etc. 205:and 174:log 164:log 139:and 80:and 64:and 54:list 44:, a 8703:doi 8610:doi 8577:doi 8318:doi 8277:doi 8238:doi 8208:doi 8157:doi 7915:doi 7836:doi 7744:doi 7728:An 7698:doi 7467:). 7371:CPU 6913:log 6469:log 6463:log 6447:log 6395:log 6338:log 6332:log 6213:log 6181:log 6129:No 6096:log 6051:log 6006:log 5948:No 5924:1.5 5918:log 5904:log 5874:1.5 5868:log 5854:log 5824:1.5 5818:log 5804:log 5734:No 5663:No 5630:log 5590:log 5553:log 5411:or 5401:No 5283:No 5255:log 5221:log 5187:log 5093:No 4965:No 4843:No 4840:No 4762:No 4759:No 4642:≪ 2 4634:No 4631:No 4460:No 4457:No 4337:No 4187:No 3985:is 3981:If 3815:is 3811:If 3704:No 3480:≪ 2 3338:≪ 2 3266:No 3155:No 3011:No 2811:No 2262:No 2176:log 2149:No 2047:log 2020:No 1962:log 1930:log 1892:No 1871:log 1812:log 1780:log 1757:n-1 1721:log 1689:log 1646:in 1636:No 1608:log 1576:log 1546:n-1 1510:log 1478:log 1438:An 1432:No 1406:log 1374:log 1277:log 1245:log 1177:log 1145:log 1113:log 1086:No 1058:log 1026:log 994:log 925:log 893:log 861:log 838:STL 830:No 809:log 780:log 748:log 716:log 690:No 664:log 632:log 600:log 541:log 360:key 40:In 9731:: 8905:, 8897:, 8844:, 8810:, 8785:. 8781:. 8756:. 8752:. 8727:. 8723:. 8699:79 8670:. 8664:. 8616:. 8604:. 8600:. 8573:27 8571:, 8539:; 8535:; 8531:; 8462:. 8458:. 8428:. 8402:. 8398:. 8324:. 8314:82 8312:. 8308:. 8283:. 8244:. 8234:42 8232:. 8204:40 8202:. 8173:, 8163:, 8096:; 8085:^ 8059:; 8055:; 8051:; 8038:^ 8021:. 8015:. 7981:; 7977:; 7973:; 7947:. 7943:. 7921:. 7911:21 7909:. 7842:. 7834:. 7820:. 7812:. 7782:. 7778:. 7750:. 7734:. 7722:; 7718:; 7696:. 7684:35 7647:; 7643:; 7639:; 7560:. 7478:. 7332:· 7074:. 6950:. 6741:. 6544:. 6524:, 6139:. 5977:. 5498:. 5415:. 5090:— 4962:— 4857:— 4654:— 4358:— 4229:— 4051:. 3891:— 3881:. 3721:— 3610:— 3494:— 3391:Θ( 2377:. 2364:+ 1661:. 1450:. 1346:. 1217:. 526:— 523:— 462:. 273:). 225:. 213:, 209:, 197:, 193:, 160:Ω( 143:. 122:. 9272:e 9265:t 9258:v 9013:e 9006:t 8999:v 8986:. 8970:. 8856:. 8797:. 8767:. 8738:. 8709:. 8705:: 8681:. 8638:. 8612:: 8606:2 8579:: 8474:. 8444:. 8414:. 8360:. 8332:. 8320:: 8293:. 8279:: 8252:. 8240:: 8214:. 8210:: 8188:. 8159:: 8135:. 8129:: 8114:. 8079:. 8032:. 7959:. 7929:. 7917:: 7889:. 7852:. 7838:: 7797:. 7760:. 7746:: 7704:. 7700:: 7625:. 7602:. 7575:. 7449:k 7441:k 7437:k 7401:k 7334:k 7330:n 7326:k 7322:n 7276:n 7272:S 7267:S 7263:i 7259:i 7255:S 7251:n 7247:S 7243:n 7239:S 7235:S 7180:n 7126:n 7122:n 7056:n 7052:n 7048:n 7046:( 7044:O 7040:n 7038:( 7036:O 7025:n 7023:( 7021:O 7005:) 7002:n 6999:k 6996:( 6993:O 6966:. 6931:) 6928:n 6925:( 6917:2 6906:2 6903:+ 6900:1 6890:n 6886:n 6879:n 6875:n 6871:n 6860:n 6856:n 6848:n 6844:n 6840:n 6836:n 6829:n 6825:n 6821:n 6784:n 6780:n 6776:n 6772:n 6712:n 6708:n 6704:n 6670:n 6662:n 6658:n 6654:n 6650:n 6638:n 6627:n 6625:( 6623:O 6500:n 6498:( 6496:O 6481:) 6475:n 6457:/ 6453:n 6444:n 6440:( 6436:O 6426:n 6424:( 6422:O 6407:) 6401:n 6390:n 6386:( 6382:O 6369:n 6367:( 6365:O 6350:) 6344:n 6327:n 6323:( 6319:O 6302:n 6300:( 6298:O 6294:) 6292:n 6288:n 6286:( 6284:O 6272:n 6268:n 6266:( 6264:O 6254:) 6252:n 6250:( 6248:O 6235:1 6219:n 6210:n 6187:n 6178:n 6124:n 6105:) 6102:n 6093:( 6086:n 6060:) 6057:n 6048:( 6041:n 6015:) 6012:n 6003:( 5996:n 5971:) 5969:n 5967:( 5965:O 5961:n 5959:( 5957:O 5943:n 5914:/ 5910:3 5900:n 5864:/ 5860:3 5850:n 5814:/ 5810:3 5800:n 5768:) 5765:! 5762:n 5756:n 5753:( 5750:O 5730:1 5709:) 5706:! 5703:n 5697:n 5694:( 5681:n 5659:1 5642:n 5634:2 5626:n 5602:n 5594:2 5565:n 5557:2 5492:n 5488:n 5486:( 5484:O 5459:2 5455:n 5441:n 5434:n 5427:n 5397:1 5378:2 5374:n 5346:2 5342:n 5314:2 5310:n 5261:n 5252:n 5227:n 5218:n 5193:n 5184:n 5164:S 5148:) 5145:S 5142:( 5139:O 5115:) 5112:n 5109:( 5106:O 5073:2 5069:n 5055:S 5048:S 5041:n 5000:n 4998:( 4996:O 4946:d 4942:2 4938:+ 4935:n 4912:d 4909:k 4901:n 4878:d 4875:k 4867:n 4836:n 4819:2 4815:n 4793:r 4790:+ 4787:n 4776:n 4743:d 4740:k 4732:n 4709:d 4706:k 4698:n 4675:d 4672:k 4664:n 4640:n 4615:d 4611:2 4602:d 4599:k 4575:) 4571:d 4568:+ 4563:s 4560:k 4554:( 4547:n 4524:d 4521:k 4513:n 4502:n 4479:1 4475:/ 4471:k 4441:1 4437:2 4413:1 4410:k 4402:n 4379:1 4376:k 4368:n 4342:n 4318:d 4314:2 4310:+ 4307:n 4284:d 4281:k 4273:n 4250:d 4247:k 4239:n 4202:d 4199:k 4168:d 4164:2 4160:+ 4157:n 4134:d 4131:k 4123:n 4100:d 4097:k 4089:n 4068:n 4037:) 4034:n 4031:( 4028:O 4004:) 4001:n 3998:( 3995:O 3983:r 3961:r 3958:+ 3955:n 3934:r 3931:+ 3928:n 3907:r 3904:+ 3901:n 3867:) 3864:n 3861:( 3858:O 3834:) 3831:n 3828:( 3825:O 3813:r 3791:r 3788:+ 3785:n 3764:r 3761:+ 3758:n 3737:r 3734:+ 3731:n 3687:k 3681:n 3660:k 3652:2 3648:n 3626:k 3623:+ 3620:n 3577:k 3573:2 3549:k 3545:2 3541:+ 3538:n 3515:k 3511:2 3507:+ 3504:n 3478:n 3444:k 3440:, 3425:d 3422:k 3417:2 3405:n 3399:) 3397:n 3393:n 3384:, 3369:d 3366:k 3358:n 3336:n 3328:r 3324:d 3320:k 3316:n 3304:) 3302:n 3298:n 3296:( 3294:Ω 3262:1 3244:2 3240:n 3214:2 3210:n 3184:2 3180:n 3151:1 3133:2 3129:n 3103:2 3099:n 3073:2 3069:n 3036:) 3033:n 3030:( 3027:O 3007:1 2989:2 2985:n 2959:2 2955:n 2929:2 2925:n 2896:n 2877:2 2873:n 2847:2 2843:n 2829:n 2807:1 2789:2 2785:n 2759:2 2755:n 2741:n 2719:1 2701:2 2697:n 2671:2 2667:n 2653:n 2631:1 2613:2 2609:n 2583:2 2579:n 2565:n 2543:1 2525:2 2521:n 2495:2 2491:n 2477:n 2455:1 2437:2 2433:n 2407:2 2403:n 2389:n 2372:d 2368:) 2366:d 2362:n 2360:( 2358:O 2346:1 2328:2 2324:n 2298:2 2294:n 2280:n 2258:1 2240:2 2236:n 2210:2 2206:n 2182:n 2173:n 2145:1 2127:2 2123:/ 2119:3 2115:n 2089:3 2085:/ 2081:4 2077:n 2053:n 2044:n 2015:n 1996:2 1992:n 1968:n 1959:n 1936:n 1927:n 1907:) 1905:n 1901:O 1877:n 1846:2 1842:n 1818:n 1809:n 1786:n 1777:n 1744:n 1727:n 1718:n 1695:n 1686:n 1673:n 1659:) 1657:n 1653:n 1651:( 1649:O 1631:n 1614:n 1605:n 1582:n 1573:n 1560:n 1533:n 1516:n 1507:n 1484:n 1475:n 1462:n 1428:1 1412:n 1403:n 1380:n 1371:n 1358:n 1328:) 1325:n 1322:( 1319:O 1299:1 1283:n 1274:n 1251:n 1242:n 1229:n 1202:n 1183:n 1174:n 1151:n 1142:n 1119:n 1110:n 1081:n 1064:n 1055:n 1032:n 1023:n 1000:n 991:n 971:) 969:n 965:O 948:n 931:n 922:n 899:n 890:n 867:n 858:n 815:n 786:n 777:n 754:n 745:n 722:n 713:n 686:1 670:n 661:n 638:n 629:n 606:n 597:n 569:1 553:n 545:2 537:n 479:) 477:n 473:n 471:( 469:O 449:. 447:) 445:n 438:n 412:n 380:♥ 376:♦ 374:( 326:. 290:n 271:n 267:n 263:n 259:n 255:n 251:n 176:n 172:n 168:) 166:n 162:n 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index