{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/27112","repository_url":"https://api.github.com/repos/JuliaLang/julia","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/27112/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/27112/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/27112/events","html_url":"https://github.com/JuliaLang/julia/issues/27112","id":323391860,"number":27112,"title":"sortperm docs & stability","user":{"login":"haampie","id":194764,"avatar_url":"https://avatars3.githubusercontent.com/u/194764?v=4","gravatar_id":"","url":"https://api.github.com/users/haampie","html_url":"https://github.com/haampie","followers_url":"https://api.github.com/users/haampie/followers","following_url":"https://api.github.com/users/haampie/following{/other_user}","gists_url":"https://api.github.com/users/haampie/gists{/gist_id}","starred_url":"https://api.github.com/users/haampie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haampie/subscriptions","organizations_url":"https://api.github.com/users/haampie/orgs","repos_url":"https://api.github.com/users/haampie/repos","events_url":"https://api.github.com/users/haampie/events{/privacy}","received_events_url":"https://api.github.com/users/haampie/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-05-15T21:34:48Z","updated_at":"2018-05-15T21:59:22Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"There's a couple issues with the docs and the internals of `sortperm`. The docs say:\r\n\r\n>     sortperm(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)\r\n> Return a permutation vector of indices of `v` that puts it in sorted order. Specify `alg` to\r\nchoose a particular sorting algorithm (see Sorting Algorithms). `MergeSort` is used by\r\ndefault, and since it is stable, the resulting permutation will be the lexicographically\r\nfirst one that puts the input array into sorted order – i.e. indices of equal elements\r\nappear in ascending order. If you choose a non-stable sorting algorithm such as `QuickSort`,\r\na different permutation that puts the array into order may be returned. The order is\r\nspecified using the same keywords as `sort!`.\r\n\r\n1. The default algorithm is `DEFAULT_UNSTABLE`, but the docs mention it's stable (MergeSort).\r\n2. Even if one selects an unstable algorithm, the actual permutation is _always_ stable, because the `Perm` ordering is defined first by value, then by index.\r\n\r\nWhat should the desired behaviour be?\r\n\r\nI'd say: make sortperm's default algorithm DEFAULT_STABLE, remove the part in the binary op of Perm that forces stable sort. That way we have stable sort by default, but people can opt out if they need better performance."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/389327051","html_url":"https://github.com/JuliaLang/julia/issues/27112#issuecomment-389327051","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/27112","id":389327051,"user":{"login":"haampie","id":194764,"avatar_url":"https://avatars3.githubusercontent.com/u/194764?v=4","gravatar_id":"","url":"https://api.github.com/users/haampie","html_url":"https://github.com/haampie","followers_url":"https://api.github.com/users/haampie/followers","following_url":"https://api.github.com/users/haampie/following{/other_user}","gists_url":"https://api.github.com/users/haampie/gists{/gist_id}","starred_url":"https://api.github.com/users/haampie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haampie/subscriptions","organizations_url":"https://api.github.com/users/haampie/orgs","repos_url":"https://api.github.com/users/haampie/repos","events_url":"https://api.github.com/users/haampie/events{/privacy}","received_events_url":"https://api.github.com/users/haampie/received_events","type":"User","site_admin":false},"created_at":"2018-05-15T21:59:22Z","updated_at":"2018-05-15T21:59:22Z","author_association":"CONTRIBUTOR","body":"But after `alg::Algorithm=DEFAULT_STABLE`, should we change\r\n\r\n```\r\nfunction lt(p::Perm, a::Integer, b::Integer)\r\n    da = p.data[a]\r\n    db = p.data[b]\r\n    lt(p.order, da, db) | (!lt(p.order, db, da) & (a < b))\r\nend\r\n```\r\n\r\nto\r\n\r\n```\r\nlt(p::Perm, a::Integer, b::Integer) = lt(p.order, p.data[a], p.data[b])\r\n```\r\n?\r\n"}}
{"actor":{"display_login":"haampie"}}