Practice Now
std::sort
algorithm
memory usage
C++
sorting algorithms

stdsort algorithms memory usage

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsC & C++

Introduction

std::sort in C++ uses an introsort hybrid — quicksort for the fast average case, heapsort as a fallback when quicksort degrades, and insertion sort for small partitions. Its memory usage is O(log n) for the recursion stack, with no additional heap allocation. The algorithm sorts in-place, meaning it rearranges elements within the existing array without allocating a separate copy. This makes it suitable for memory-constrained environments.

How std::sort Works Internally

The C++ standard requires std::sort to be O(n log n) in the worst case (since C++11). Most implementations use introsort, which combines three algorithms:

 
1introsort(array, depth_limit):
2    if size <= 16:
3        insertion_sort(array)     // O(1) extra space
4    else if depth_limit == 0:
5        heapsort(array)           // O(1) extra space
6    else:
7        pivot = partition(array)  // O(1) extra space
8        introsort(left_half, depth_limit - 1)   // O(log n) stack
9        introsort(right_half, depth_limit - 1)  // tail-call optimized

The depth limit is typically 2 * log2(n). If quicksort's recursion exceeds this limit (indicating a bad pivot sequence), it switches to heapsort.

Memory Usage Breakdown

ComponentSpaceReason
Quicksort partitionO(1)Swaps elements in-place using a pivot
Recursion stackO(log n)Each recursive call uses a constant-size stack frame
Heapsort fallbackO(1)Builds heap in-place, no extra allocation
Insertion sortO(1)Shifts elements in-place
TotalO(log n)All from the recursion stack
cpp
1#include <algorithm>
2#include <vector>
3
4std::vector<int> v = {5, 3, 8, 1, 9, 2, 7};
5std::sort(v.begin(), v.end());
6// Sorts in-place — no additional vector or array allocated
7// Stack usage: ~log2(7) ≈ 3 recursive frames

Stack Usage in Practice

Each recursive call pushes a stack frame containing local variables (iterators, pivot value, depth counter). A typical frame is 50-100 bytes:

 
1For n = 1,000,000 elements:
2  Max recursion depth = 2 * log2(1,000,000) ≈ 40
3  Stack usage ≈ 40 frames * ~80 bytes = ~3.2 KB
4
5For n = 1,000,000,000 elements:
6  Max recursion depth ≈ 60
7  Stack usage ≈ 60 * ~80 bytes = ~4.8 KB

This is negligible compared to the data itself.

Comparison with Other Sorting Algorithms

AlgorithmTime (avg)Time (worst)Extra SpaceStable?
std::sort (introsort)O(n log n)O(n log n)O(log n)No
std::stable_sort (mergesort)O(n log n)O(n log n)O(n)Yes
std::partial_sort (heapsort)O(n log k)O(n log k)O(1)No
std::nth_element (introselect)O(n)O(n)O(log n)No
cpp
1// std::stable_sort allocates O(n) extra memory
2std::vector<int> v = {5, 3, 8, 1, 9};
3std::stable_sort(v.begin(), v.end());
4// Internally allocates a temporary buffer of ~n elements
5// Uses merge sort — preserves relative order of equal elements

Why std::sort Is Not Stable

In-place quicksort does not preserve the relative order of equal elements. When stability matters (sorting records by one field while preserving prior ordering), use std::stable_sort:

cpp
1struct Employee {
2    std::string name;
3    int department;
4};
5
6std::vector<Employee> employees = {/*...*/};
7
8// Unstable — equal department values may be reordered
9std::sort(employees.begin(), employees.end(),
10    [](const Employee& a, const Employee& b) {
11        return a.department < b.department;
12    });
13
14// Stable — preserves original order within same department
15std::stable_sort(employees.begin(), employees.end(),
16    [](const Employee& a, const Employee& b) {
17        return a.department < b.department;
18    });
19// stable_sort uses O(n) extra memory for the merge buffer

Measuring Memory Usage

cpp
1#include <algorithm>
2#include <vector>
3#include <iostream>
4#include <cstdlib>
5
6// Custom allocator to track allocations (simplified)
7static size_t total_allocated = 0;
8
9void* operator new(size_t size) {
10    total_allocated += size;
11    return std::malloc(size);
12}
13
14int main() {
15    std::vector<int> v(1000000);
16    std::iota(v.begin(), v.end(), 0);
17    std::shuffle(v.begin(), v.end(), std::mt19937{42});
18
19    total_allocated = 0;
20    std::sort(v.begin(), v.end());
21    std::cout << "std::sort allocated: " << total_allocated << " bytes\n";
22    // Output: 0 bytes (no heap allocation)
23
24    total_allocated = 0;
25    std::shuffle(v.begin(), v.end(), std::mt19937{42});
26    std::stable_sort(v.begin(), v.end());
27    std::cout << "std::stable_sort allocated: " << total_allocated << " bytes\n";
28    // Output: ~4000000 bytes (n * sizeof(int) temporary buffer)
29}

Implementation-Specific Details

GCC (libstdc++)

Uses introsort with insertion sort threshold of 16 elements. The __introsort_loop function tail-call optimizes the right partition, reducing stack depth.

Clang (libc++)

Uses a similar introsort approach with additional optimizations for small arrays and partially sorted data.

MSVC (STL)

Uses introsort with insertion sort for small partitions. Recent versions add special handling for already-sorted ranges.

When Memory Matters

cpp
1// Embedded systems with limited stack (e.g., 4KB):
2// std::sort uses ~40-60 stack frames max
3// At ~80 bytes per frame, worst case is ~5KB
4// Consider iterative quicksort or heapsort if stack is very tight
5
6// For large objects, sort indices instead:
7std::vector<LargeStruct> data(1000000);
8std::vector<size_t> indices(data.size());
9std::iota(indices.begin(), indices.end(), 0);
10
11std::sort(indices.begin(), indices.end(),
12    [&data](size_t a, size_t b) {
13        return data[a].key < data[b].key;
14    });
15// Sorts 8-byte indices instead of swapping large structs

Common Pitfalls

  • Assuming std::sort allocates heap memory: It does not. All extra space is on the stack (O(log n) frames). Only std::stable_sort allocates heap memory.
  • Stack overflow with deep recursion: Introsort prevents this by switching to heapsort after 2 * log2(n) depth. Pure quicksort without this safeguard can hit O(n) recursion depth on adversarial input.
  • Confusing std::sort with std::stable_sort memory: std::sort uses O(log n) space; std::stable_sort uses O(n). Choose based on whether you need stability.
  • Sorting large objects by value: std::sort swaps elements. For 1KB structs, each swap copies 1KB three times. Sort pointers or indices instead to minimize data movement.
  • Custom comparators with side effects: The comparator must be a strict weak ordering. Non-deterministic or stateful comparators can cause infinite loops or stack overflow in the partition logic.

Summary

  • std::sort uses O(log n) extra space — all from the recursion stack, no heap allocation
  • It combines quicksort (fast average), heapsort (guaranteed worst case), and insertion sort (small arrays)
  • std::stable_sort uses O(n) extra heap memory for its merge buffer
  • For memory-constrained systems, std::sort is safe — even for a billion elements, stack usage is under 5KB
  • Sort indices instead of large objects to minimize swap overhead
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.