storage needed additionally to that used by the list itself, under the same assumption. The run times and the memory requirements listed are inside big O notation, hence the base of the logarithms does not matter. The notation means . Comparison sorts Below is a table of comparison sorts. A comparison sort cannot perform better than on average. Non-comparison sorts The following table describes integer sorting algorithms and other sorting algorithms that are not comparison sorts. As such, they are not limited to Ω(n log n). Complexities below assume items to be sorted, with keys of size , digit size , and the range of numbers to be sorted. 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 , where ≪ means "much less than". In the unit-cost random-access machine model, algorithms with running time of , such as radix sort, still take time proportional to , because is limited to be not more than , and a larger number of elements to sort would require a bigger in order to store them in the memory. Samplesort 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. Others Some algorithms are slow compared to those discussed above, such as the bogosort with unbounded run time and the stooge sort which has O(n2.7) 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. Theoretical computer scientists have detailed other sorting algorithms that provide better than O(n log n) time complexity assuming additional constraints, including: Thorup's algorithm, a randomized algorithm for sorting keys from a domain of finite size, taking time and O(n) space. A randomized integer sorting algorithm taking expected time and O(n) space. One of the authors of the previously mentioned algorithm also claims to have discovered an algorithm taking time and O(n) space, sorting real numbers. Further claiming that, without any added assumptions on the input, it can be modified to achieve time and O(n) space. Popular sorting algorithms