Sorting Algorithms

The most basic sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in wrong order. Like bubbles rising to the surface, larger values gradually move to the end of the array. Best suited for small datasets or educational purposes to understand sorting fundamentals.

Finds the smallest element and moves it to the front repeatedly. Each iteration "selects" the minimum from remaining elements and places it after the sorted portion. Simple to implement with minimal memory usage, but always takes O(n²) time regardless of input.

A highly efficient sorting algorithm that selects a pivot element and partitions the array with smaller values on the left and larger on the right. Averages O(n log n) and is the most widely used sorting method in practice. Forms the foundation of built-in sort functions in most programming languages.

Uses a binary heap data structure by first building a max heap, then repeatedly extracting the root element to sort. Guarantees O(n log n) time complexity in all cases without requiring extra memory. Also serves as the foundation for priority queue implementations.

A non-comparison sorting algorithm that counts occurrences of each element and uses arithmetic to determine positions. Achieves O(n+k) time complexity where k is the range of input values. Ideal for sorting integers within a known, limited range. Forms the basis for radix sort.

A non-comparison sorting algorithm that processes elements digit by digit from least significant to most significant. Uses counting sort as a subroutine for each digit position. Achieves O(d(n+k)) time where d is the number of digits. Excellent for sorting integers or fixed-length strings.

An optimization of insertion sort that allows exchange of elements that are far apart. Uses a gap sequence that decreases to 1, enabling the algorithm to move elements closer to their final positions faster. Named after Donald Shell who invented it in 1959.

A distribution-based sorting algorithm that distributes elements into a number of buckets. Each bucket is then sorted individually using another sorting algorithm. Works best when input is uniformly distributed over a range. Average time complexity is O(n+k).

A divide-and-conquer algorithm that splits the array in half, sorts each half recursively, then merges them back together. Guarantees O(n log n) time and is stable, but requires additional memory. Particularly effective for large datasets and linked list sorting.

Works like sorting playing cards in your hands - inserting each element one at a time into its proper position. Runs in O(n) time for already sorted data, making it highly efficient for small arrays or nearly sorted datasets. Simple yet adaptive algorithm.

Improvement over bubble sort that eliminates small values near the end of the list (turtles). Uses a shrinking gap sequence starting with array length, improving worst-case complexity. Practical for medium-sized datasets where simple implementation is valued over optimal performance.

Simple sorting algorithm similar to insertion sort, named after the way garden gnomes sort flower pots. Moves backward when elements are out of order, then forward again. While O(n²) like bubble sort, its simplicity makes it useful for teaching sorting concepts and handling small datasets.