#
5f358716 |
|
17-Jul-2023 |
Colin Percival <cperciva@FreeBSD.org> |
Add <sys/queue_mergesort.h> Thie file provides macros for performing mergesorts and merging two sorted lists implemented by <sys/queue.h>. The mergesort operates in guaranteed O(n log n) time and uses constant additional space: 3 or 4 pointers (depending on list type) and 4 size_t values. The merge operates in guaranteed O(n + m) time and uses constant additional space: 3 pointers. In memoriam: hselasky Reviewed by: jhb (previous version) Sponsored by: https://www.patreon.com/cperciva Differential Revision: https://reviews.freebsd.org/D41073
|