Partition vs Stable Partition Performance

The partition() and stable_partition() algorithms in C++ are used to divide a collection into two parts based on a predicate, but they differ significantly in terms of performance.

partition()

The partition() algorithm is designed for speed and efficiency. It rearranges elements within the collection based on the predicate without caring about the order of elements within each partition.

This lack of order preservation means partition() can often be implemented with fewer swaps and less overhead, making it faster and more efficient in terms of time complexity.

It typically operates in $O(n)$ time, where n is the number of elements in the collection.

stable_partition()

On the other hand, stable_partition() preserves the relative order of elements within each partition. This means that if two elements are equal according to the predicate, their order in the original collection is maintained in the resulting partitions.

While this stability is useful in many scenarios, it comes at a performance cost. To maintain this order, stable_partition() generally requires additional temporary storage and more complex operations, resulting in higher time and space complexity compared to partition().

It often operates in $O(n log n)$ time due to the need for additional operations to maintain order. Here’s a comparison in code:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> A = {1, -6, 7, 2, 5, 4};
7
8  // Using partition()
9  std::ranges::partition(A, [](int x) {
10    return x < 0; });
11
12  std::cout << "After partition: ";
13  for (int x : A) std::cout << x << ", ";
14
15  // Using stable_partition()
16  std::ranges::stable_partition(A, [](int x) {
17    return x < 0; });
18
19  std::cout << "\nAfter stable_partition: ";
20  for (int x : A) std::cout << x << ", ";
21}

1After partition: -6, 2, 7, 1, 5, 4,
2After stable_partition: -6, 1, 7, 2, 5, 4,

In this example, partition() is faster but may not maintain the order of elements. stable_partition() maintains the order but at a higher computational cost.

Choose between them based on whether maintaining the order of elements is crucial for your application.