{"action":"created","issue":{"url":"https://api.github.com/repos/swenson/sort/issues/47","repository_url":"https://api.github.com/repos/swenson/sort","labels_url":"https://api.github.com/repos/swenson/sort/issues/47/labels{/name}","comments_url":"https://api.github.com/repos/swenson/sort/issues/47/comments","events_url":"https://api.github.com/repos/swenson/sort/issues/47/events","html_url":"https://github.com/swenson/sort/issues/47","id":374368699,"node_id":"MDU6SXNzdWUzNzQzNjg2OTk=","number":47,"title":"Is the tim sort implemented stable?","user":{"login":"liwt31","id":22628546,"node_id":"MDQ6VXNlcjIyNjI4NTQ2","avatar_url":"https://avatars3.githubusercontent.com/u/22628546?v=4","gravatar_id":"","url":"https://api.github.com/users/liwt31","html_url":"https://github.com/liwt31","followers_url":"https://api.github.com/users/liwt31/followers","following_url":"https://api.github.com/users/liwt31/following{/other_user}","gists_url":"https://api.github.com/users/liwt31/gists{/gist_id}","starred_url":"https://api.github.com/users/liwt31/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liwt31/subscriptions","organizations_url":"https://api.github.com/users/liwt31/orgs","repos_url":"https://api.github.com/users/liwt31/repos","events_url":"https://api.github.com/users/liwt31/events{/privacy}","received_events_url":"https://api.github.com/users/liwt31/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-10-26T12:48:33Z","updated_at":"2018-10-26T15:51:14Z","closed_at":"2018-10-26T15:51:14Z","author_association":"NONE","body":"I noticed the following code in tim sort:\r\n\r\n> https://github.com/swenson/sort/blob/d360ba02ca55803673ead2497d352135a9aa291e/sort.h#L737-L747\r\n\r\nIf the run in `dst` contains duplicate elements in the middle, they are pairwise swapped here, hence making tim sort unstable.\r\n\r\nNow sure if I'm right or wrong - I'm new to tim sort and trying to learn from your code, so I apologize if I have made any mistakes.\r\n"},"comment":{"url":"https://api.github.com/repos/swenson/sort/issues/comments/433454742","html_url":"https://github.com/swenson/sort/issues/47#issuecomment-433454742","issue_url":"https://api.github.com/repos/swenson/sort/issues/47","id":433454742,"node_id":"MDEyOklzc3VlQ29tbWVudDQzMzQ1NDc0Mg==","user":{"login":"swenson","id":33404,"node_id":"MDQ6VXNlcjMzNDA0","avatar_url":"https://avatars3.githubusercontent.com/u/33404?v=4","gravatar_id":"","url":"https://api.github.com/users/swenson","html_url":"https://github.com/swenson","followers_url":"https://api.github.com/users/swenson/followers","following_url":"https://api.github.com/users/swenson/following{/other_user}","gists_url":"https://api.github.com/users/swenson/gists{/gist_id}","starred_url":"https://api.github.com/users/swenson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/swenson/subscriptions","organizations_url":"https://api.github.com/users/swenson/orgs","repos_url":"https://api.github.com/users/swenson/repos","events_url":"https://api.github.com/users/swenson/events{/privacy}","received_events_url":"https://api.github.com/users/swenson/received_events","type":"User","site_admin":false},"created_at":"2018-10-26T15:51:14Z","updated_at":"2018-10-26T15:51:14Z","author_association":"OWNER","body":"Yes, tim sort is implemented stably.\r\n\r\n`REVERSE_ELEMENTS` is only called in one place: when there is a strictly decreasing run of elements. https://github.com/swenson/sort/blob/d360ba02ca55803673ead2497d352135a9aa291e/sort.h#L796\r\n\r\nPart of the stress testing is to check that it is stable as well (though of course, there could always be a bug).\r\n\r\nThanks for checking!"}}
{"actor":{"display_login":"swenson"}}