Editing Sorting algorithm (section)

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

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

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

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

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