`merge_sort::sort` causes double free

[kaixinlalala]

Description:

Calling algorithmica::sort::merge_sort::sort with a vector of owned values such as String
causes a double free.

The README lists Merge Sort as a supported sorting algorithm, and the public API accepts generic
types with T: Ord + Debug. There is no documented restriction that T must be Copy or that
owned heap-allocated values are unsupported. Therefore, sorting Vec<String> should be a valid use
case.

However, the implementation uses ptr::read() to move values out of slices and temporary vectors
without preventing the original locations from being dropped. This creates multiple owners of the
same allocation and eventually leads to double free.

Environment:

algorithmica version: 0.1.10
rustc version: 1.94.1
OS: Ubuntu 20.04.6 LTS
Command:

RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --target x86_64-unknown-linux-gnu

PoC

extern crate algorithmica;

fn main() {
    let mut v = vec!["b".to_string(), "a".to_string()];
    algorithmica::sort::merge_sort::sort(&mut v);
}

Expected behavior:

The sort should complete normally and print the sorted vector:

["a", "b"]

Actual behavior

==59989==ERROR: AddressSanitizer: attempting double-free on 0x7bb3c35e0030 in thread T0:
    #0 0x561551f09e76  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd3e76) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #1 0x561551f3bb9a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x105b9a) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #2 0x561551f3bb73  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x105b73) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #3 0x561551f3bbaa  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x105baa) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #4 0x561551f388bd  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x1028bd) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #5 0x561551f38ad0  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102ad0) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #6 0x561551f38812  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102812) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #7 0x561551f39845  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x103845) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #8 0x561551f3919a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10319a) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #9 0x561551f39298  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x103298) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #10 0x561551f3b2a8  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x1052a8) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #11 0x561551f38aea  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102aea) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #12 0x561551f38f6d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102f6d) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #13 0x561551f3afb0  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x104fb0) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #14 0x561551f62135  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x12c135) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #15 0x561551f3af1f  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x104f1f) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #16 0x561551f3b41d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10541d) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #17 0x7f93c40dc082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082) (BuildId: 5792732f783158c66fb4f3756458ca24e46e827d)
    #18 0x561551e7e1ed  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x481ed) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)

0x7bb3c35e0030 is located 0 bytes inside of 1-byte region [0x7bb3c35e0030,0x7bb3c35e0031)
freed by thread T0 here:
    #0 0x561551f09e76  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd3e76) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #1 0x561551f3bb9a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x105b9a) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #2 0x561551f3919a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10319a) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #3 0x561551f38aea  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102aea) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #4 0x561551f3af1f  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x104f1f) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #5 0x561551f3b41d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10541d) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)

previously allocated by thread T0 here:
    #0 0x561551f0a114  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd4114) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #1 0x561551f6be38  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x135e38) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #2 0x561551f3bd25  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x105d25) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #3 0x561551f3b79b  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10579b) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #4 0x561551f38d29  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102d29) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #5 0x561551f38aea  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102aea) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #6 0x561551f3af1f  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x104f1f) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)
    #7 0x561551f3b41d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10541d) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1)

SUMMARY: AddressSanitizer: double-free (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd3e76) (BuildId: 3ee867d1cb71075871de175dd16c4577a84504c1) 
==59989==ABORTING

Root cause:

The problem is in src/sort/merge_sort.rs.

The implementation first copies values out of the original slice using ptr::read():

left.push(get_by_index(list, start as isize).read());

and:

right.push(get_by_index(list, start as isize).read());

Later, it copies values out of the temporary left and right vectors, again using ptr::read():

list[k] = get_by_index(&left, left_index as isize).read();

For types like String, ptr::read() performs a bitwise move. It does not clone the heap buffer, and it does not mark the original location as uninitialized. This is undefined behavior and can be triggered through safe public APIs.