Skip to content

Improve documentation of slice::sort_by_key and slice::sort_unstable_by_key #71132

New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Closed
MiSawa opened this issue Apr 14, 2020 · 0 comments · Fixed by #71133
Closed

Improve documentation of slice::sort_by_key and slice::sort_unstable_by_key #71132

MiSawa opened this issue Apr 14, 2020 · 0 comments · Fixed by #71133
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@MiSawa
Copy link
Contributor

MiSawa commented Apr 14, 2020

The current documentation for slice::sort_by_key and slice::sort_unstable_by_key method claims that for a slice of n elements, the method takes O(m n log(m n)) worst-case, where the key function is O(m).

rust/src/liballoc/slice.rs

Lines 257 to 258 in d28a464

/// This sort is stable (i.e., does not reorder equal elements) and `O(m n log(m n))`
/// worst-case, where the key function is `O(m)`.

Although this is not wrong, this time complexity is not tight and can be replaced with O(m n log n) as far as my understanding.

Brief explanation relying on another doc claiming the time complexity of merge_sort, which slice::sort_by_key relies on, is O(n log n) worst-case;
Since its running time is O(n log n), merge_sort can call is_less only O(n log n) times. Each call of is_less makes 2 calls of the key function, so the total time complexity taken by the key function is O((2 n log n) * m) = O(m n log n).
Because other part of merge_sort takes O(n log n) as the doc states, its total running time is O(n log n + m n log n) = O(m n log n).
Exact same discussion applies to sort_unstable_by_key + sort::quicksort.

@jonas-schievink jonas-schievink added C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. labels Apr 14, 2020
@bors bors closed this as completed in 54b160d Apr 15, 2020
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants