History log of /freebsd-current/sys/sys/queue_mergesort.h
Revision Date Author Comments
# 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