libc/src/stdlib/heap_sort.h

   1 //===-- Implementation of heap sort -----------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H
  10 #define LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H
  11
  12 #include "src/__support/CPP/cstddef.h"
  13 #include "src/stdlib/qsort_data.h"
  14
  15 namespace LIBC_NAMESPACE_DECL {
  16 namespace internal {
  17
  18 // A simple in-place heapsort implementation.
  19 // Follow the implementation in https://en.wikipedia.org/wiki/Heapsort.
  20
  21 LIBC_INLINE void heap_sort(const Array &array) {
  22   size_t end = array.size();
  23   size_t start = end / 2;
  24
  25   auto left_child = [](size_t i) -> size_t { return 2 * i + 1; };
  26
  27   while (end > 1) {
  28     if (start > 0) {
  29       // Select the next unheapified element to sift down.
  30       --start;
  31     } else {
  32       // Extract the max element of the heap, moving a leaf to root to be sifted
  33       // down.
  34       --end;
  35       array.swap(0, end);
  36     }
  37
  38     // Sift start down the heap.
  39     size_t root = start;
  40     while (left_child(root) < end) {
  41       size_t child = left_child(root);
  42       // If there are two children, set child to the greater.
  43       if (child + 1 < end &&
  44           array.elem_compare(child, array.get(child + 1)) < 0)
  45         ++child;
  46
  47       // If the root is less than the greater child
  48       if (array.elem_compare(root, array.get(child)) >= 0)
  49         break;
  50
  51       // Swap the root with the greater child and continue sifting down.
  52       array.swap(root, child);
  53       root = child;
  54     }
  55   }
  56 }
  57
  58 } // namespace internal
  59 } // namespace LIBC_NAMESPACE_DECL
  60
  61 #endif // LLVM_LIBC_SRC_STDLIB_HEAP_SORT_H