Master 8 Essential Sorting Algorithms: From Insertion to Radix

Sorting can be classified into internal sorting (all records fit in memory) and external sorting (requires external storage). The following algorithms are internal sorts.

8 Major Sorting Algorithms Explained

Insertion Sort

In a list where the first (n‑1) elements are already sorted, the nth element is inserted into its correct position among the sorted part, repeating until the whole list is ordered.

Shell Sort (Diminishing Increment Sort)

The list is divided into groups based on a gap d (initially n/2). Each group undergoes insertion sort, then the gap is reduced (d/2) and the process repeats until the gap becomes 1, after which a final insertion sort completes the ordering.

Selection Sort

The smallest element is selected and swapped with the first position, then the next smallest is swapped with the second position, and so on until the list is sorted.

Heap Sort

Heap sort builds a binary heap (max‑heap) from the array, repeatedly swaps the root (largest element) with the last element of the heap, reduces the heap size, and restores the heap property, resulting in a sorted sequence.

Bubble Sort

Adjacent elements are compared and swapped if they are in the wrong order, causing larger elements to "bubble" to the end of the list with each pass.

Quick Sort

A pivot element (often the first or last) partitions the array into elements less than the pivot and elements greater or equal, then the sub‑arrays are recursively sorted.

Merge Sort

Merge sort divides the array into sorted sub‑arrays and then merges them to produce a fully sorted array.

Radix Sort

All numbers are padded to the same length. Starting from the least significant digit, a stable sort is performed on each digit position, resulting in a sorted list after the most significant digit is processed.

Algorithm Complexity Details

Time Complexity

Time complexity describes how the execution time grows with input size n, expressed using Big‑O notation such as O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), etc.

Worst‑case time complexity is usually discussed; average‑case complexity considers all inputs with equal probability.

Space Complexity

Space complexity measures the memory required by an algorithm, including a fixed part (code, constants, static variables) and a variable part (dynamic allocations, recursion stack). It is expressed as S(n)=O(f(n)).