DOCSEARCHbyAlgolia
Submit Docs

glidesort

repository·master·Indexed 23 days ago

https://github.com/orlp/glidesort

A stable, deterministic, comparison-based sorting algorithm for Rust that combines Timsort-style merge sort benefits for pre-sorted data with pattern-defeating quicksort benefits for data with many duplicates. It provides functions like sort, sort_by, and sort_by_key, along with memory-management options such as sort_with_buffer and sort_in_vec to reuse auxiliary space.

Tokens
715
Snippets
1
Records
12
Agent score
32%

What's inside glidesort

  1. Glidesort performance characteristics

    master

    Glidesort is a stable, deterministic, comparison-based sort. For sorting n elements with k distinct values, its complexity is:

    CaseComplexity
    Bestn
    Averagen log k
    Worstn log n
    Memoryn / 8 (default)

    Memory Management: By default, Glidesort allocates up to n elements worth of data. It scales this down if it exceeds 1 MiB (to n / 2) or 1 GiB (to n / 8). If provided with O(1) memory, the average and worst cases become O(n (log n)^2), though performance remains good for most data sizes.

  2. Use Glidesort for basic sorting

    master

    Glidesort provides stable sorting functions that can replace standard library sorting calls. You can use glidesort::sort for default comparison, or sort_by and sort_by_key for custom comparison logic.

    To use it, replace a.sort() with glidesort::sort(&mut a).

  4. Enable comparison tracking with the `tracking` feature

    master
    If the tracking feature is enabled, the sorting functions will call tracking::register_cmp for every comparison made. This is useful for debugging or analyzing the sorting process.

  5. Use glidesort::sort_with_buffer for custom auxiliary space

    master

    If you want to manage the auxiliary memory used by the algorithm, use glidesort::sort_with_buffer. This function requires you to pass a &mut [MaybeUninit<T>] buffer, which the algorithm will use exclusively as its scratch space.

    This interface also supports _by and _by_key variants.

  6. Use glidesort::sort_in_vec to reuse auxiliary space

    master
    To reduce allocations in scenarios where you perform multiple sorts, use glidesort::sort_in_vec(&mut v). This function behaves like the standard sort but allocates its auxiliary space at the end of the provided Vec<T>. This allows future sorting calls to re-use the same space.

  9. Sort a `Vec` in-place with `sort_in_vec` family

    master
    The sort_in_vec family of functions sorts a Vec<T> and allocates the necessary scratch space at the end of the existing Vec's capacity. This is efficient if the Vec has sufficient spare capacity.

  10. Reuse allocation with `sort_with_vec` family

    master
    To avoid repeated dynamic allocations when sorting multiple slices, use the sort_with_vec family of functions. These functions take a mutable reference to a Vec<T> which acts as a scratch buffer. The buffer is resized using reserve as needed.

  11. Sort using a provided buffer with `sort_with_buffer` family

    master
    If you want to manage your own memory and avoid all dynamic allocations within the library, use the sort_with_buffer family. These functions require you to provide a slice of MaybeUninit<T> to serve as the scratch space.