std::stable_sort

Use case

Sort while preserving relative order of equivalent elements.

Explanation

Slightly slower than std::sort due to stability guarantee.

Time complexity: O(n log n) with extra memory, worse than O(n log n) without. The extra memory is necessary for merge sort. See possible implementation.

Code

#include <algorithm>
#include <cstdint>
#include <print>
#include <string>
#include <vector>

struct Symbol {
  uint64_t address;
  std::string name;
  int order;
};

int main() {
  std::vector<Symbol> symbols = {{0x1000, "_init", 0},
                                 {0x1080, "_helper", 1},
                                 {0x1040, "_main", 2},
                                 {0x1040, "main", 3},
                                 {0x1040, "_start", 4}};

  std::stable_sort(
      symbols.begin(), symbols.end(),
      [](const Symbol &a, const Symbol &b) { return a.address < b.address; });

  for (const auto &sym : symbols) {
    std::println("{:#x} {} (was #{})", sym.address, sym.name, sym.order);
  }

  return 0;
}

View on GitHub.

Output

$ ./src/algorithms/build/std-stable_sort
0x1000 _init (was #0)
0x1040 _main (was #2)
0x1040 main (was #3)
0x1040 _start (was #4)
0x1080 _helper (was #1)