Explore 8 Essential Sorting Algorithms and Their Trade‑offs

Sorting algorithms are divided into internal (in‑memory) and external (disk‑based) sorts. Common internal sorts include insertion, shell, selection, bubble, merge, quick, heap, and radix sorts, which are introduced below.

Insertion Sort

Shell Sort

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

Heap Sort

Radix Sort

Algorithm 1: Insertion Sort

Insertion sort builds a sorted sequence by scanning the unsorted part from back to front and inserting each element into its proper position.

Algorithm steps:

1) Treat the first element as a sorted sub‑array and the rest as unsorted.

2) Scan the unsorted part, inserting each element into the correct place in the sorted sub‑array (equal elements are placed after existing ones).

Algorithm 2: Shell Sort

Shell sort, also called diminishing‑increment sort, is an improved version of insertion sort but is not stable.

- Insertion sort is efficient for nearly sorted data, achieving near‑linear performance.
- However, insertion sort moves elements only one position at a time, making it inefficient for random data.

The basic idea is to divide the array into sub‑sequences using a gap sequence, sort each sub‑sequence with insertion sort, and repeat with decreasing gaps until the gap is 1.

Algorithm steps:

1) Choose a gap sequence t1, t2, …, tk where ti > tj and tk = 1.

2) Perform k passes of sorting using the gaps.

3) For each pass, split the array into sub‑arrays of length m according to the current gap and apply direct insertion sort; when the gap is 1, treat the whole array as a single list.

Algorithm 3: Selection Sort

Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the end of the sorted portion.

Algorithm steps:

1) Find the minimum (or maximum) element in the unsorted part and place it at the beginning of the sorted part.

2) Continue selecting the next minimum (or maximum) from the remaining unsorted elements and append it.

3) Repeat until all elements are sorted.

Algorithm 4: Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, causing larger elements to “bubble” to the end.

Algorithm steps:

1) Compare each pair of adjacent elements and swap if the first is greater.

2) After each pass, the largest unsorted element moves to its final position.

3) Repeat the passes for the remaining unsorted portion until no swaps are needed.

Algorithm 5: Merge Sort

Merge sort is a classic divide‑and‑conquer algorithm that recursively splits the array, sorts the halves, and merges them.

Algorithm steps:

Allocate space equal to the sum of the two sorted sub‑arrays.

Initialize two pointers at the start of each sub‑array.

Compare the pointed elements, copy the smaller one into the merged space, and advance that pointer.

Repeat until one sub‑array is exhausted.

Copy the remaining elements of the other sub‑array into the merged space.

Algorithm 6: Quick Sort

Quick sort, developed by Tony Hoare, uses a divide‑and‑conquer strategy to partition the list around a pivot element.

Algorithm steps:

1) Choose a pivot element.

2) Rearrange the list so that elements smaller than the pivot come before it and larger elements come after it.

3) Recursively apply the same process to the sub‑lists on each side of the pivot.

The recursion stops when sub‑lists have zero or one element.

Algorithm 7: Heap Sort

Heap sort builds a binary heap (a nearly complete tree) and repeatedly extracts the maximum (or minimum) element to produce a sorted array.

Algorithm steps:

1) Build a heap H[0..n‑1].

2) Swap the root (maximum) with the last element.

3) Reduce the heap size by one and heapify the new root (shift_down).

4) Repeat steps 2‑3 until the heap size is 1.

Algorithm 8: Radix Sort

Radix sort is a non‑comparison integer sorting algorithm that processes digits from least‑significant to most‑significant (or vice‑versa) using a stable sub‑sorting method such as counting or bucket sort.

Before radix sort, bucket sort is introduced: the array is distributed into a fixed number of buckets, each bucket is sorted individually (often with another simple sort), and the buckets are concatenated.

Radix sort can achieve linear time O(n) when the number of digits (or buckets) is proportional to the input size, but it requires additional space for the buckets.

Summary of Complexity and Stability

Time complexity categories:

Quadratic O(n²): Insertion, Selection, Bubble.

Linearithmic O(n log n): Quick, Heap, Merge.

Sub‑linear‑logarithmic O(n·logⁿ): Shell.

Linear O(n): Radix (and bucket/box sorts).

Stability:

Stable sorts: Bubble, Insertion, Merge, Radix.

Unstable sorts: Selection, Quick, Shell, Heap.

Original source: http://www.cricode.com/3212.html Author: 快课网——Jay13