Index out of bounds in `heap_sort::sink` due to off-by-one error

[Rohan-GRH]

Hi, I encountered an index out of bounds panic when invoking the sink function in heap_sort.rs. The crash occurs at line 42, where the bounds check j < n is insufficient — when j = n - 1, the condition is true but arr[j + 1] accesses index n, which is out of bounds. The related source code is shown below:
[algorithmica/src/sort/heap_sort.rs](

algorithmica/algorithmica/src/sort/heap_sort.rs

Lines 35 to 52 in 073d556

	/// This operation happens when given root `k` is become lesser than it,s
	/// children. Because we are maintaining the MaxHeap, so both child should
	/// be lesser than it's parent
	pub fn sink<T: Ord, F: Fn(&T, &T) -> bool>(arr: &mut [T], k: usize, n: usize, p: &F) {
	let mut k = k;
	while 2 * k < n {
	let mut j = 2 * k + 1;
	if j < n && p(&arr[j], &arr[j + 1]) {
	j += 1;
	}
	if !p(&arr[j], &arr[k]) {
	arr.swap(k, j);
	k = j;
	} else {
	break;
	}
	}
	}

)

The bug is on line 42: the guard j < n ensures arr[j] is valid, but does NOT ensure arr[j + 1] is valid. When j = n - 1, the code accesses arr[n] which is out of bounds.

The panic report is:

Panic: index out of bounds: the len is 6 but the index is 6
Location: algorithmica/src/sort/heap_sort.rs:42:33

stack backtrace:
  0: __rustc::rust_begin_unwind
        at /rustc/1d23d06800271f651fad07bf22bf5e298138972e/library/std/src/panicking.rs:698:5
  1: core::panicking::panic_fmt
        at /rustc/1d23d06800271f651fad07bf22bf5e298138972e/library/core/src/panicking.rs:80:14
  2: core::panicking::panic_bounds_check
        at /rustc/1d23d06800271f651fad07bf22bf5e298138972e/library/core/src/panicking.rs:276:5
  3: algorithmica::sort::heap_sort::sink
        at algorithmica/src/sort/heap_sort.rs:42:33

This crash is likely to be a bug of the library and can cause security issues.

How to reproduce it:

The PoC program is:

use algorithmica::sort::heap_sort::sink;

fn main() {
    let mut arr: Vec<u8> = vec![5, 3, 8, 1, 2, 7];
    let n = arr.len();  // n = 6
    let k = 0;
    sink(&mut arr, k, n, &|a: &u8, b: &u8| a < b);
    // panics: "index out of bounds: the len is 6 but the index is 6"
}

The build command is like:

export RUSTFLAGS="-Zsanitizer=address -C opt-level=0 -C debuginfo=2"
export RUSTUP_TOOLCHAIN="nightly"

cargo +nightly afl build --target x86_64-unknown-linux-gnu

Environment:

• Discovered via fuzz testing
• OS / distro: Ubuntu 24.04