Sorting Algorithms
Simple Sorts O(n²)
A simple comparison-based algorithm that repeatedly swaps adjacent elements if they are in the wrong order. While inefficient for large datasets, it's easy to understand and implement, making it excellent for educational purposes.
- O(n²) time complexity
- O(1) space complexity
- Stable sorting algorithm
- Simple to understand and implement
- Swaps adjacent elements
- Adaptive - performs well on nearly sorted data
Finds the minimum element in the unsorted portion and places it at the beginning. While still O(n²), it minimizes the number of swaps, making it useful when write operations are expensive.
- O(n²) time complexity
- O(1) space complexity
- Unstable sorting algorithm
- Fewer swaps than bubble sort
- In-place sorting
- Finds minimum in each iteration
Builds the sorted array one element at a time by inserting each element into its correct position. Efficient for small or nearly sorted datasets and can sort data as it's received (online algorithm).
- O(n²) time complexity
- O(1) space complexity
- Stable sorting algorithm
- Excellent for small datasets
- Adaptive - O(n) for nearly sorted data
- Online algorithm - can sort streaming data
Efficient Sorts O(n log n)
A divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and merges the results. Offers predictable O(n log n) performance but requires extra space for merging.
- O(n log n) time complexity
- O(n) space complexity
- Stable sorting algorithm
- Divide-and-conquer strategy
- Predictable performance - no worst case
- Not in-place - requires auxiliary space
A divide-and-conquer algorithm that selects a pivot and partitions the array around it. Generally faster than other O(n log n) algorithms due to cache efficiency, though it can degrade to O(n²) with poor pivot selection.
- O(n log n) average time
- O(n²) worst case time
- O(log n) space complexity
- Unstable sorting algorithm
- In-place sorting
- Pivot-based partitioning
- Cache-friendly - good locality of reference
Uses a binary heap data structure to sort elements. Guarantees O(n log n) performance with O(1) space complexity, making it ideal when space is limited and worst-case performance matters.
- O(n log n) time complexity
- O(1) space complexity
- Unstable sorting algorithm
- In-place sorting
- Uses binary heap structure
- No worst-case degradation
- Not adaptive
Specialized Sorts
A non-comparison based algorithm that counts occurrences of each element. Works only with integer keys within a limited range, but can be extremely fast (linear time) for suitable data.
- O(n + k) time complexity
- O(k) space complexity
- Stable sorting algorithm
- Integer keys only
- Limited range required
- Not comparison-based
- Linear time for suitable data
Sorts integers or strings by processing individual digits or characters from least significant to most significant (LSD) or vice versa (MSD). Non-comparison based and can be very fast for appropriate data types.
- O(d(n + k)) time complexity
- O(n + k) space complexity
- Stable sorting algorithm
- Digit-by-digit processing
- Works with integers and strings
- LSD (least significant digit) or MSD variants
- Not comparison-based
Distributes elements into buckets, sorts each bucket individually, and concatenates results. Works well with uniformly distributed data but can degrade to O(n²) if distribution is poor.
- O(n + k) average time
- O(n²) worst case time
- Space depends on bucket count
- Requires uniform distribution
- Divides data into buckets
- Sorts each bucket separately
- Not comparison-based
Hybrid & Practical Sorts
A hybrid stable sorting algorithm combining merge sort and insertion sort. Designed to perform well on real-world data with existing order. Used as the default sort in Python and Java.
- O(n log n) time complexity
- O(n) space complexity
- Stable sorting algorithm
- Hybrid merge sort + insertion sort
- Optimized for real-world data
- Exploits existing order in data
- Default in Python and Java
A hybrid algorithm that begins with quick sort and switches to heap sort when recursion depth exceeds a threshold. Provides quick sort's average-case speed with heap sort's worst-case guarantee.
- O(n log n) time complexity
- O(log n) space complexity
- Unstable sorting algorithm
- Hybrid quick sort + heap sort
- Worst-case O(n log n) guarantee
- Default in C++ STL
- Switches algorithms to avoid worst case