Space and Time Complexities of Common Sorting Algorithms in TheAlgorithms/Python

The TheAlgorithms/Python repository implements classic sorting algorithms with documented asymptotic complexities ranging from O(n²) for simple comparison sorts like bubble and insertion sort to O(n log n) for efficient divide-and-conquer methods like merge sort and tim sort, with space requirements varying from O(1) in-place sorts to O(n) auxiliary storage.

The sorts package in the TheAlgorithms/Python repository contains educational implementations of fundamental sorting algorithms, each with distinct performance characteristics. Understanding the space and time complexities of common sorting algorithms is essential for selecting the right algorithm based on your data size, memory constraints, and distribution. This analysis examines the asymptotic complexities documented in the source code for comparison-based sorts, non-comparison linear sorts, and hybrid approaches.

Comparison Sorts with O(n²) Complexity

Bubble Sort

In sorts/bubble_sort.py, both iterative and recursive implementations exhibit O(n²) average and worst-case time complexity. The algorithm requires only O(1) auxiliary space, operating in-place by repeatedly swapping adjacent elements until the list is ordered. While simple and stable, this quadratic time makes it unsuitable for large datasets.

Selection Sort

The selection_sort() function in sorts/selection_sort.py performs O(n²) comparisons regardless of input order, performing exactly n-1 swaps in the worst case. It uses O(1) extra space but is not stable, as it swaps non-adjacent elements that may change the relative order of equal keys.

Insertion Sort

Found in sorts/insertion_sort.py, insertion sort also runs in O(n²) time for average and worst cases, but achieves O(n) best-case performance when the input is nearly sorted. It requires O(1) additional space and is stable, making it efficient for small or partially ordered datasets despite its quadratic worst-case bound.

Efficient O(n log n) Comparison Sorts

Merge Sort

The merge_sort() implementation in sorts/merge_sort.py uses a divide-and-conquer strategy that guarantees O(n log n) time complexity in all cases. However, it requires O(n) auxiliary space to merge subarrays, as the implementation returns a new sorted list rather than modifying the input in-place. This stability comes at the cost of linear memory overhead.

Quick Sort

As implemented in sorts/quick_sort.py, this algorithm achieves O(n log n) average-case time using a random-pivot strategy, though it degrades to O(n²) when pivot selection consistently hits extremes. The space complexity is O(log n) on average due to the recursion stack, though the specific implementation uses list operations that are not strictly in-place.

Heap Sort

The heap_sort() function in sorts/heap_sort.py builds a max-heap to achieve O(n log n) time complexity in all cases while using only O(1) extra space. This in-place behavior makes it memory-efficient compared to merge sort, though it is not stable and typically has higher constant factors than quick sort.

Tim Sort

sorts/tim_sort.py implements Python's hybrid algorithm combining insertion sort for small runs and merge sort for consolidation. It maintains O(n log n) worst-case time with O(n) space complexity for temporary run storage. This is the same algorithm used by CPython's built-in list.sort(), optimized for real-world data with existing order.

Linear Time Non-Comparison Sorts

Counting Sort

Located in sorts/counting_sort.py, this algorithm runs in O(n + k) time where k is the range of input values, using O(k) auxiliary space for the counting array. It is stable and efficient when k is small relative to n, but impractical for large integer ranges.

Bucket Sort

The bucket_sort() implementation in sorts/bucket_sort.py distributes elements into buckets for O(n + k) average-case time, though it degrades to O(n²) worst-case when all elements land in a single bucket. It requires O(n + k) space to store the buckets, performing best on uniformly distributed data.

Radix Sort

In sorts/radix_sort.py, the LSD (least significant digit) approach processes d digits with base b, yielding O(d·(n + b)) time complexity and O(n + b) space. This stable, non-comparison sort efficiently handles fixed-width integers when the number of digits is small relative to n.

Hybrid and Specialized Algorithms

Shell Sort

sorts/shell_sort.py generalizes insertion sort with a gap sequence, typically achieving O(n^{1.5}) time depending on the specific gap sequence chosen. It requires only O(1) extra space, offering better performance than simple insertion sort without the memory overhead of merge-based approaches.

Comb Sort

The sorts/comb_sort.py implementation improves upon bubble sort using a shrinking gap, with empirical average complexity better than O(n²) though still O(n²) worst-case. Like bubble sort, it operates in-place with O(1) space.

Cocktail Shaker Sort

Found in sorts/cocktail_shaker_sort.py, this bidirectional bubble sort maintains O(n²) time and O(1) space complexity while potentially reducing the number of passes needed for some inputs by bubbling elements in both directions.

Practical Implementation Examples

To utilize these algorithms from the repository, import the specific functions from the sorts package. Each accepts a mutable sequence and returns a new sorted list (or modifies in-place where noted).

# Example dataset

data = [34, -2, 7, 0, 23, 5]

# O(n²) algorithms

from sorts.bubble_sort import bubble_sort_iterative
from sorts.selection_sort import selection_sort
from sorts.insertion_sort import insertion_sort

print("Bubble:", bubble_sort_iterative(data.copy()))
print("Selection:", selection_sort(data.copy()))
print("Insertion:", insertion_sort(data.copy()))

# O(n log n) algorithms

from sorts.merge_sort import merge_sort
from sorts.quick_sort import quick_sort
from sorts.heap_sort import heap_sort
from sorts.tim_sort import tim_sort

print("Merge:", merge_sort(data.copy()))
print("Quick:", quick_sort(data.copy()))
print("Heap:", heap_sort(data.copy()))
print("Tim:", tim_sort(data.copy()))

# Linear time algorithms (for appropriate data types)

from sorts.counting_sort import counting_sort
from sorts.bucket_sort import bucket_sort
from sorts.radix_sort import radix_sort

# Note: Counting sort requires non-negative integers

print("Counting:", counting_sort([x for x in data if x >= 0]))
print("Bucket:", bucket_sort(data.copy()))
print("Radix:", radix_sort([abs(x) for x in data]))

Summary

• Quadratic time sorts (bubble, selection, insertion) in sorts/bubble_sort.py, sorts/selection_sort.py, and sorts/insertion_sort.py use O(1) space but only scale to small datasets.
• Efficient comparison sorts (merge, quick, heap, tim) achieve O(n log n) time, with merge and tim sorts requiring O(n) space while heap sort operates in-place with O(1) auxiliary memory.
• Non-comparison sorts (counting, bucket, radix) in sorts/counting_sort.py, sorts/bucket_sort.py, and sorts/radix_sort.py achieve linear O(n) time when key ranges are limited, trading space for speed.
• Specialized hybrids like shell sort and comb sort offer middle-ground performance with minimal memory overhead.

Frequently Asked Questions

What is the difference between time complexity and space complexity in sorting?

Time complexity measures how the number of operations grows with input size n, determining runtime scalability. Space complexity measures the additional memory required beyond the input storage, ranging from O(1) for in-place algorithms like heap sort to O(n) for merge sort's auxiliary arrays.

Why does Quick Sort have O(n²) worst-case time complexity?

In sorts/quick_sort.py, the worst case occurs when the random pivot consistently selects the minimum or maximum element, creating maximally unbalanced partitions. This forces the algorithm to process n levels of recursion with O(n) work per level, resulting in O(n²) total operations despite the O(n log n) average case.

When should I use Counting Sort over Quick Sort?

Use counting_sort() from sorts/counting_sort.py when sorting integers with a small, known range k where k = O(n), achieving O(n + k) linear time. Quick sort's O(n log n) comparison-based approach is preferable for general data or when the value range exceeds the dataset size significantly, as counting sort's O(k) space becomes prohibitive.

Which sorting algorithm in TheAlgorithms/Python uses the least memory?

Heap sort (heap_sort() in sorts/heap_sort.py) and bubble sort (bubble_sort_iterative in sorts/bubble_sort.py) both use O(1) auxiliary space, modifying the input list in-place. Among efficient O(n log n) algorithms, heap sort offers the best space complexity compared to merge sort's O(n) requirement or quick sort's O(log n) recursion stack.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}