Master the Eight Classic Internal Sorting Algorithms: Steps, Complexity, and Stability

Insertion Sort

Builds a sorted prefix by taking each element from the unsorted suffix and inserting it into its correct position in the prefix.

Treat the first element as a sorted sub‑array; the rest is unsorted.

Iterate over the unsorted part, shifting larger elements of the sorted sub‑array rightward until the correct slot for the current element is found, then insert it.

Shell Sort

An extension of insertion sort that uses a decreasing gap sequence to partially sort the array.

Select a gap sequence t1, t2, …, tk with tk = 1.

For each gap ti, perform a gapped insertion sort: split the array into ti interleaved sub‑arrays and sort each with insertion sort.

When the gap reaches 1, the whole array is sorted.

Selection Sort

Repeatedly selects the minimum (or maximum) element from the unsorted region and swaps it into the next position of the sorted region.

Find the smallest element in the unsorted portion.

Swap it with the first element of the unsorted portion.

Continue until the array is sorted.

Bubble Sort

Repeatedly scans the list, swapping adjacent out‑of‑order elements so that larger values “bubble” to the end.

Compare each adjacent pair and swap if the left element is larger.

After each full pass, the largest remaining element is placed at its final index.

Repeat passes on the reduced unsorted prefix until a pass makes no swaps.

Merge Sort

A divide‑and‑conquer algorithm that recursively splits the array and merges sorted halves.

Recursively split the array until sub‑arrays of size 1 are obtained.

During merge, allocate a temporary buffer equal to the combined size of the two sub‑arrays.

Use two pointers to repeatedly copy the smaller pointed element into the buffer, advancing the corresponding pointer.

When one sub‑array is exhausted, copy the remainder of the other.

Copy the merged buffer back into the original array segment.

Quick Sort

Uses divide‑and‑conquer with a pivot element.

Choose a pivot (commonly the first, last, or median element).

Partition the array so that elements < pivot are left of the pivot and elements > pivot are right.

Recursively apply quicksort to the left and right partitions.

Base case: sub‑array size 0 or 1.

Heap Sort

Builds a binary max‑heap and repeatedly extracts the maximum element.

Transform the input array into a max‑heap (heapify).

Swap the root (maximum) with the last element of the heap.

Reduce the heap size by one and heapify the new root (shift‑down).

Repeat until only one element remains.

Radix Sort

A non‑comparison integer sort that processes digits from least‑significant to most‑significant, typically using counting/bucket sort as a stable sub‑routine.

For each digit position (starting with the least significant), distribute elements into buckets based on that digit.

Collect the buckets in order to form a new sequence.

Repeat for the next more significant digit until the most significant digit has been processed.

Radix sort runs in O(n) time when the number of buckets is proportional to n, but requires additional space and assumes a known bounded key range.

Complexity and Stability Summary

Time complexity O(n²): Insertion, Selection, Bubble. O(n log n): Merge, Quick, Heap. O(n^{1+α}) (0 < α < 1): Shell. O(n): Radix (and Bucket when input is uniformly distributed).

Stability

Stable: Insertion, Bubble, Merge, Radix.

Unstable: Selection, Quick, Shell, Heap.