Common Sorting Algorithms: Quick Sort, Merge Sort, Heap Sort, Selection Sort, Bubble Sort, Insertion Sort, and Shell Sort

1. Quick Sort

Introduction: Quick Sort, developed by Tony Hoare, sorts n items with an average time complexity of O ( n log n ) comparisons. In the worst case it requires O ( n 2 ) comparisons, though this is rare. In practice Quick Sort is often faster than other O ( n log n ) algorithms because its inner loop is efficiently implemented on most architectures.

Steps:

Choose an element from the array as the "pivot".

Reorder the array so that all elements smaller than the pivot are placed before it and all larger elements after it (equal elements may go either side). After this partition step the pivot is in its final position.

Recursively apply the same process to the sub‑arrays of elements less than the pivot and greater than the pivot.

Sorting effect:

2. Merge Sort

Introduction: Merge Sort is an efficient sorting algorithm based on the divide‑and‑conquer paradigm. It repeatedly splits the array, sorts the halves, and merges them back together.

Steps:

Allocate temporary space equal to the combined size of the two sorted sub‑arrays.

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

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

Repeat step 3 until one pointer reaches the end of its sub‑array.

Copy any remaining elements from the other sub‑array into the temporary space.

Sorting effect:

3. Heap Sort

Introduction: Heap Sort uses a heap data structure (a nearly complete binary tree) where each parent node satisfies the heap property: its key is greater (or smaller) than those of its children.

Steps:

(The detailed steps are complex; refer to external resources for a full description.)

Sorting effect:

4. Selection Sort

Introduction: Selection Sort repeatedly selects the smallest remaining element and moves it to the front of the unsorted portion, building the sorted array from left to right.

Sorting effect:

5. Bubble Sort

Introduction: 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 of the list.

Steps:

Compare each pair of adjacent elements; if the first is larger, swap them.

Repeat the pass from the beginning to the end; after each pass the largest unsorted element settles at the end.

Continue repeating the passes for the remaining unsorted portion until no swaps are needed.

Sorting effect:

6. Insertion Sort

Introduction: Insertion Sort builds a sorted sequence one element at a time by scanning the already sorted part from right to left, shifting larger elements to make room for the new element.

Steps:

Consider the first element as a sorted sub‑array.

Take the next element and scan the sorted sub‑array from right to left to find its correct position.

If the scanned element is larger than the new element, shift it one position to the right.

Continue shifting until an element smaller than or equal to the new element is found.

Insert the new element at that position.

Repeat from step 2 for the remaining elements.

Sorting effect:

(No visual provided.)

7. Shell Sort

Introduction: Shell Sort is a high‑speed, stable improvement of Insertion Sort that uses a decreasing gap sequence to sort elements that are far apart.

It leverages two properties of Insertion Sort: (1) it is efficient for nearly sorted data, achieving near‑linear performance; (2) plain Insertion Sort moves elements only one position at a time, which is inefficient for large gaps.

Sorting effect:

Original source: nginx