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 heap_sort(const Array & array)21LIBC_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 62