Sorting algorithm
Sorting algorithm
A sorting algorithm is a method for arranging a collection of items (such as numbers, strings, or records) into a specific order, most commonly numerical or lexicographical. Sorting algorithms are fundamental in computer science, used as building blocks for more complex operations like Binary Search, Data Merging, and Database Indexing.
Overview
Sorting algorithms can be classified by several criteria. The most common distinction is between comparison-based and non-comparison-based sorts. Comparison sorts, such as Quicksort and Merge Sort, determine order by comparing pairs of elements using a comparison operator. Non‑comparison sorts, such as Radix Sort and Counting Sort, exploit special properties of the data (e.g., integer keys) to achieve faster asymptotic times under certain conditions.
Key properties of sorting algorithms include:
- Stability – A stable sort preserves the relative order of records with equal keys.
- In‑place – An in‑place sort requires only a constant amount of extra memory beyond the input.
- Adaptivity – An adaptive algorithm runs faster when the input is already partially sorted.
- Time complexity – Usually expressed using Big O notation, e.g., O(n log n) or O(n²).
- Space complexity – The amount of auxiliary memory needed.
History
Early mechanical sorting methods include punched card sorters used in the late 19th and early 20th centuries. The first computer sorting algorithms were developed in the 1940s and 1950s alongside stored-program computers. Bubble Sort was described by Edward H. Friend in 1956, though it was known earlier as "sorting by exchange". Insertion Sort and Selection Sort are older, often taught as textbook examples of algorithm analysis.
Notable milestones:
- 1945 – John von Neumann described Merge Sort, one of the first divide‑and‑conquer algorithms.
- 1959 – Shell Sort (named after Donald Shell) improved upon insertion sort by allowing exchanges of far‑apart elements.
- 1960 – C. A. R. Hoare invented Quicksort, which remains widely used for its average‑case efficiency.
- 1964 – Heap Sort was proposed by J. W. J. Williams, combining the speed of Quicksort with O(n log n) worst‑case performance.
- 1970s – Bucket Sort, Radix Sort, and Counting Sort were refined for specialised data types.
Common sorting algorithms
- Bubble Sort – Simple but inefficient (O(n²)), often used for teaching.
- Insertion Sort – Efficient on small or nearly sorted datasets; O(n²) worst case.
- Selection Sort – O(n²) comparisons but minimal data movement.
- Merge Sort – Stable, O(n log n) worst case, requires O(n) extra space.
- Quicksort – In‑place (with O(log n) stack space), O(n²) worst case but O(n log n) average.
- Heap Sort – In‑place, O(n log n) worst case, not stable.
- Radix Sort – Non‑comparison, O(nk) for n keys of digit length k.
- Counting Sort – Linear time for integer keys within a limited range.
Applications
Sorting is used in Search Algorithms, Data Compression, Graph Algorithms (e.g., Kruskal's Algorithm requires sorting edges), and Database Management (for Indexing and Query Optimization). Many programming languages provide built‑in sorting functions (e.g., Python’s sorted() implemented using Timsort, a hybrid algorithm).