--- a/sorting.cc	Fri Apr 07 15:13:48 2023 +0200
+++ b/sorting.cc	Fri Apr 07 15:50:41 2023 +0200
@@ -5,6 +5,8 @@
 #include <algorithm>
 #include <functional>
 #include <iostream>
+#include <ranges>
+#include <span>
 #include <string>
 #include <utility>
 #include <vector>
@@ -119,7 +121,7 @@
     return make_pair(2*i+1, 2*i+2);
 }
 
-template<typename T> void heap_sift_down(vector<T>& v, size_t i) {
+template<typename T> void heap_sift_down(span<T> v, size_t i) {
     if (i >= v.size())
         return;
 
@@ -130,22 +132,22 @@
         return;
     else if (get<1>(children) >= v.size()) {
         size_t left = get<0>(children);
-        T& target = v.at(i) > v.at(left) ? v.at(i) : v.at(left);
-        swap(target, v.at(i));
+        T& target = v[i] > v[left] ? v[i] : v[left];
+        swap(target, v[i]);
         return;
     }
 
-    T& left = v.at(get<0>(children)), &right = v.at(get<1>(children));
+    T& left = v[get<0>(children)], &right = v[get<1>(children)];
     // Order already correct.
-    if (max(left, right) < v.at(i))
+    if (max(left, right) < v[i])
         return;
 
     // Recur:
     if (left > right) {
-        swap(v.at(i), left);
+        swap(v[i], left);
         heap_sift_down(v, get<0>(children));
     } else {
-        swap(v.at(i), right);
+        swap(v[i], right);
         heap_sift_down(v, get<1>(children));
     }
 }
@@ -170,7 +172,7 @@
 void make_into_heap(vector<T>& v, SiftDirection direction = SiftDirection::Down) {
     if (direction == SiftDirection::Down)
         for (ssize_t i = v.size()-1; i >= 0; i--) {
-                heap_sift_down(v, i);
+                heap_sift_down(span(v), i);
         }
     else
         for (size_t i = 0; i < v.size(); i++) {
@@ -179,11 +181,27 @@
 }
 
 
+template<typename T>
+void flatten_heap(vector<T>& v) {
+    for (int i = v.size()-1; i > 0; i--) {
+        swap(v[0], v[i]);
+        heap_sift_down(span(v.begin(), v.begin()+i), 0);
+    }
+}
+
+//template<typename T, typename R> requires (range<R> and is_same<range_value_t<R>, T>)
+template<typename T>
+void heap_sort(vector<T>& rng) {
+    make_into_heap(rng);
+    flatten_heap(rng);
+    return;
+}
+
 int main(void) {
     vector<string> v{"hello", "olleh", "abc", "bca", "world", "wrlod"};
     vector<int> vi{5,5,6,1,3,2,5,8,9};
 
-    timeit_f([&vi]() -> void { quicksort(vi); }, "quicksort");
+    timeit_f([&vi]() { heap_sort(vi); }, "heapsort");
     fmt::print("{}\n", vi);
     return 0;
 }