fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <chrono>
  4.  
  5. const std::size_t SIZE = 3000;
  6.  
  7. // =====================================================================
  8. // 1. C++14 Constexpr Array & Helpers
  9. // =====================================================================
  10. template <typename T, std::size_t N>
  11. struct CXArray {
  12.     T data[N];
  13.     constexpr T& operator[](std::size_t i) { return data[i]; }
  14.     constexpr const T& operator[](std::size_t i) const { return data[i]; }
  15.     constexpr T* begin() { return data; }
  16.     constexpr T* end() { return data + N; }
  17.     constexpr const T* begin() const { return data; }
  18.     constexpr const T* end() const { return data + N; }
  19. };
  20.  
  21. template <typename T>
  22. constexpr void cx_swap(T& a, T& b) {
  23.     T tmp = a; a = b; b = tmp;
  24. }
  25.  
  26. // =====================================================================
  27. // 2. Algorithm 1: Insertion Sort (The Finisher)
  28. // =====================================================================
  29. template <typename T, std::size_t N>
  30. constexpr void cx_insertion_sort(CXArray<T, N>& arr, int left, int right) {
  31.     for (int i = left + 1; i <= right; ++i) {
  32.         T key = arr[i];
  33.         int j = i - 1;
  34.         while (j >= left && arr[j] > key) {
  35.             arr[j + 1] = arr[j];
  36.             j--;
  37.         }
  38.         arr[j + 1] = key;
  39.     }
  40. }
  41.  
  42. // =====================================================================
  43. // 3. Algorithm 2: Heapsort (The Fallback for bad Quicksort behavior)
  44. // =====================================================================
  45. template <typename T, std::size_t N>
  46. constexpr void cx_sift_down(CXArray<T, N>& arr, int left, int length, int i) {
  47.     while (true) {
  48.         int largest = i;
  49.         int left_child = 2 * i + 1;
  50.         int right_child = 2 * i + 2;
  51.  
  52.         if (left_child < length && arr[left + left_child] > arr[left + largest]) {
  53.             largest = left_child;
  54.         }
  55.         if (right_child < length && arr[left + right_child] > arr[left + largest]) {
  56.             largest = right_child;
  57.         }
  58.         if (largest == i) break;
  59.  
  60.         cx_swap(arr[left + i], arr[left + largest]);
  61.         i = largest;
  62.     }
  63. }
  64.  
  65. template <typename T, std::size_t N>
  66. constexpr void cx_heap_sort(CXArray<T, N>& arr, int left, int right) {
  67.     int length = right - left + 1;
  68.     if (length <= 1) return;
  69.  
  70.     // Build Max Heap
  71.     for (int i = length / 2 - 1; i >= 0; --i) {
  72.         cx_sift_down(arr, left, length, i);
  73.     }
  74.     // Extract Max elements
  75.     for (int i = length - 1; i > 0; --i) {
  76.         cx_swap(arr[left], arr[left + i]);
  77.         cx_sift_down(arr, left, i, 0); // Sift down with reduced heap size
  78.     }
  79. }
  80.  
  81. // =====================================================================
  82. // 4. Algorithm 3: The Introsort Strategy (Quicksort Manager)
  83. // =====================================================================
  84. template <typename T, std::size_t N>
  85. constexpr void cx_introsort_loop(CXArray<T, N>& arr, int left, int right, int depth_limit) {
  86.     // STRATEGY 3: Stop early if partition is tiny. Leave it for Insertion Sort.
  87.     if (right - left <= 16) {
  88.         return; 
  89.     }
  90.  
  91.     // STRATEGY 2: If recursion is too deep, switch to Heapsort to guarantee O(N log N)
  92.     if (depth_limit == 0) {
  93.         cx_heap_sort(arr, left, right);
  94.         return;
  95.     }
  96.  
  97.     // STRATEGY 1: Standard Quicksort Partitioning
  98.     T pivot = arr[left + (right - left) / 2];
  99.     int i = left;
  100.     int j = right;
  101.  
  102.     while (i <= j) {
  103.         while (arr[i] < pivot) i++;
  104.         while (arr[j] > pivot) j--;
  105.  
  106.         if (i <= j) {
  107.             cx_swap(arr[i], arr[j]);
  108.             i++;
  109.             j--;
  110.         }
  111.     }
  112.  
  113.     // Recurse with less depth limit
  114.     if (left < j) cx_introsort_loop(arr, left, j, depth_limit - 1);
  115.     if (i < right) cx_introsort_loop(arr, i, right, depth_limit - 1);
  116. }
  117.  
  118. // The master wrapper that initiates the Strategy
  119. template <typename T, std::size_t N>
  120. constexpr CXArray<T, N> generate_introsort(CXArray<T, N> arr) {
  121.     // Calculate recursion limit: 2 * log2(N)
  122.     int depth_limit = 0;
  123.     int n = N;
  124.     while (n > 0) { 
  125.         n >>= 1; 
  126.         depth_limit++; 
  127.     }
  128.     depth_limit *= 2;
  129.  
  130.     // Phase 1: Heavy lifting (Quicksort + Heapsort fallback)
  131.     cx_introsort_loop(arr, 0, N - 1, depth_limit);
  132.  
  133.     // Phase 2: Final cleanup (Insertion Sort on the 16-element chunks)
  134.     cx_insertion_sort(arr, 0, N - 1);
  135.  
  136.     return arr;
  137. }
  138.  
  139. // =====================================================================
  140. // Compile-Time Evaluation Trigger
  141. // =====================================================================
  142. constexpr CXArray<int, SIZE> generate_random_data() {
  143.     CXArray<int, SIZE> arr{};
  144.     unsigned int seed = 98765;
  145.     for (std::size_t i = 0; i < SIZE; ++i) {
  146.         seed = (1103515245 * seed + 12345) % 2147483648; 
  147.         arr[i] = seed % 100000;
  148.     }
  149.     return arr;
  150. }
  151.  
  152. // 💥 COMPILER EXECUTES INTROSORT HERE 💥
  153. constexpr auto unsorted_data = generate_random_data();
  154. constexpr auto sorted_data = generate_introsort(unsorted_data);
  155.  
  156. // =====================================================================
  157. // Benchmark Engine
  158. // =====================================================================
  159. int main() {
  160.     std::cout << "Data Size: " << SIZE << " elements\n";
  161.  
  162.     // 1. Runtime Standard Sort
  163.     CXArray<int, SIZE> runtime_data = unsorted_data; 
  164.  
  165.     auto start1 = std::chrono::high_resolution_clock::now();
  166.     std::sort(runtime_data.begin(), runtime_data.end());
  167.     auto end1 = std::chrono::high_resolution_clock::now();
  168.     std::chrono::duration<double, std::milli> time_std = end1 - start1;
  169.  
  170.     // 2. Compile-Time Introsort (0ms)
  171.     auto start2 = std::chrono::high_resolution_clock::now();
  172.     volatile int dummy = sorted_data[0]; // Prevent optimization
  173.     auto end2 = std::chrono::high_resolution_clock::now();
  174.     std::chrono::duration<double, std::milli> time_cx = end2 - start2;
  175.  
  176.     std::cout << "\n--- Benchmark Results ---\n";
  177.     std::cout << "Runtime std::sort:            " << time_std.count() << " ms\n";
  178.     std::cout << "Compile-Time Introsort:       " << time_cx.count() << " ms\n";
  179.  
  180.     bool correct = std::is_sorted(sorted_data.begin(), sorted_data.end());
  181.     std::cout << "\nCompile-Time array is sorted correctly: " << (correct ? "True" : "False") << "\n";
  182.  
  183.     return 0;
  184. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Data Size: 3000 elements

--- Benchmark Results ---
Runtime std::sort:            0.102812 ms
Compile-Time Introsort:       3.3e-05 ms

Compile-Time array is sorted correctly: True
https://ideone.com/eHt8Ej
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!