Implementation:ClickHouse ClickHouse Sort

Knowledge Sources	ClickHouse
Domains	Algorithms, Performance
Last Updated	2026-02-08 00:00 GMT

Overview

Optimized sorting algorithms with debug validation and shuffle-based testing.

Description

Wraps pdqsort and miniselect with debug assertions that verify comparison functions. Adds random shuffling in debug builds to expose bugs.

Usage

Use for high-performance sorting, implementing custom comparison sorts, or validating sort stability.

Code Reference

Source Location

• Repository: ClickHouse
• File: base/base/sort.h
• Lines: 1-163

Signature

template <typename RandomIt, typename Compare>
void sort(RandomIt first, RandomIt last, Compare compare);

template <typename RandomIt>
void sort(RandomIt first, RandomIt last);

template <typename RandomIt, typename Compare>
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare compare);

template <typename RandomIt, typename Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare compare);

template <typename RandomIt, typename Compare>
bool trySort(RandomIt first, RandomIt last, Compare compare);

Import

#include <base/sort.h>

Usage Examples

#include <base/sort.h>
#include <vector>

std::vector<int> data = {5, 2, 8, 1, 9};

// Sort entire range
::sort(data.begin(), data.end());

// Sort with custom comparator
::sort(data.begin(), data.end(), [](int a, int b) { return a > b; });

// Partial sort (first n elements)
::partial_sort(data.begin(), data.begin() + 3, data.end());

// Find nth element
::nth_element(data.begin(), data.begin() + 2, data.end());

// Try fast sort (returns false if slow sort needed)
if (::trySort(data.begin(), data.end())) {
    // Data was already sorted or nearly sorted
}

Related Pages

• Principle:ClickHouse_ClickHouse_Optimized_Sorting