A sorting algorithm is a method for reorganizing a large number of items into a specific order, such as alphabetical, highest-to-lowest value, or shortest-to-longest distance. Sorting algorithms take lists of items as input data, perform specific operations on those lists, and deliver ordered arrays as output. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.
Formally, the output of any sorting algorithm must satisfy two conditions:
- The output is in monotonic order (each element is no smaller/larger than the previous element, according to the required order) .
- The output is a permutation (a reordering, without duplication, of the input) of the input.
Sorting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as big O notation, divide-and-conquer algorithms, data structures such as heaps and binary trees, randomized algorithms, best, worst and average case analysis, time–space tradeoffs, and upper and lower bounds.
Some common sorting algorithms include:
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Counting Sort
- Radix Sort
- Bucket Sort
Sorting algorithms can be categorized based on the following parameters:
- Based on the number of swaps or inversions required
- Based on the number of comparisons
- Based on recursion or non-recursion
The efficiency of any sorting algorithm is determined by the time complexity and space complexity of the algorithm.
