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

> Explore space and time complexities of common sorting algorithms in TheAlgorithms/Python. Understand O(n²) to O(n log n) performance and O(1) to O(n) space needs for efficient data sorting.

- Repository: [The Algorithms/Python](https://github.com/TheAlgorithms/Python)
- Tags: deep-dive
- Published: 2026-02-24

---

**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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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).

```python

# 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`](https://github.com/TheAlgorithms/Python/blob/main/sorts/bubble_sort.py), [`sorts/selection_sort.py`](https://github.com/TheAlgorithms/Python/blob/main/sorts/selection_sort.py), and [`sorts/insertion_sort.py`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/sorts/counting_sort.py), [`sorts/bucket_sort.py`](https://github.com/TheAlgorithms/Python/blob/main/sorts/bucket_sort.py), and [`sorts/radix_sort.py`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/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`](https://github.com/TheAlgorithms/Python/blob/main/sorts/heap_sort.py)) and **bubble sort** (`bubble_sort_iterative` in [`sorts/bubble_sort.py`](https://github.com/TheAlgorithms/Python/blob/main/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.