What sorting algorithm does list::sort use in msvc?
As far as I know, std::sort conventionally uses introsort.
However, when I look at the article here, std::list::sort says that merge sort is easy to implement, and there is no mention of which algorithm to use.
Does msvc use merge sorting?
c++ algorithm list sorting visual-c++
edited Nov 23 at 0:25
user2864740
43.5k670147
asked Nov 23 at 0:19
Exception
9
|
show 2 more comments
As far as I know, std::sort conventionally uses introsort.
However, when I look at the article here, std::list::sort says that merge sort is easy to implement, and there is no mention of which algorithm to use.
Does msvc use merge sorting?
c++ algorithm list sorting visual-c++
edited Nov 23 at 0:25
user2864740
43.5k670147
asked Nov 23 at 0:19
Exception
9
1
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
1
Implementation is in the list header,_Sort()function. Have a look. Yes, merge sort in vs2017.
– Hans Passant
Nov 23 at 1:17
|
show 2 more comments
As far as I know, std::sort conventionally uses introsort.
However, when I look at the article here, std::list::sort says that merge sort is easy to implement, and there is no mention of which algorithm to use.
Does msvc use merge sorting?
c++ algorithm list sorting visual-c++
edited Nov 23 at 0:25
user2864740
43.5k670147
asked Nov 23 at 0:19
Exception
9
As far as I know, std::sort conventionally uses introsort.
However, when I look at the article here, std::list::sort says that merge sort is easy to implement, and there is no mention of which algorithm to use.
Does msvc use merge sorting?
c++ algorithm list sorting visual-c++
c++ algorithm list sorting visual-c++
edited Nov 23 at 0:25
user2864740
43.5k670147
asked Nov 23 at 0:19
Exception
9
edited Nov 23 at 0:25
user2864740
43.5k670147
asked Nov 23 at 0:19
Exception
9
edited Nov 23 at 0:25
user2864740
43.5k670147
edited Nov 23 at 0:25
user2864740
43.5k670147
edited Nov 23 at 0:25
user2864740
43.5k670147
43.5k670147
asked Nov 23 at 0:19
Exception
9
asked Nov 23 at 0:19
Exception
9
asked Nov 23 at 0:19
Exception
9
9
1
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
1
Implementation is in the list header,_Sort()function. Have a look. Yes, merge sort in vs2017.
– Hans Passant
Nov 23 at 1:17
|
show 2 more comments
1
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
1
Implementation is in the list header,_Sort()function. Have a look. Yes, merge sort in vs2017.
– Hans Passant
Nov 23 at 1:17
1
1
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
1
1
Implementation is in the list header,
_Sort() function. Have a look. Yes, merge sort in vs2017.– Hans Passant
Nov 23 at 1:17
Implementation is in the list header,
_Sort() function. Have a look. Yes, merge sort in vs2017.– Hans Passant
Nov 23 at 1:17
|
show 2 more comments
2 Answers
2
active
oldest
votes
The algorithm was changed from bottom up to top down merge sort in Visual Studio 2015. The author of the change stated this was done to handle a list with no default allocator, but that could have been easily handled by using get_allocator() (the fix would include an instance of get_allocator() for each of the 26 elements in the array of lists) when declaring the list.
The author did note that switching to top down meant a performance hit, but correctly pointed out if performance was an issue, then in most cases, moving the list to a vector, sorting the vector, then creating a list from the sorted vector would be faster. Still, most of the STL functions are reasonably optimal, so the argument from some was that the earlier bottom up approach could be fixed to handle a no default allocator list.
Although the author did not mention this, in a discussion in the link below, it was also pointed out that the top down implementation avoided losing data if a user compare function threw an exception. However other STL functions such as std::stable_sort() will lose data if a compare function throws an exception, and my impression is exceptions created by user supplied functions aren't a priority for VS STL and should be caught with debug builds.
`std::list<>::sort()` - why the sudden switch to top-down strategy?
Wiki article includes example for both top down and bottom up merge sort for linked lists:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
answered Nov 23 at 8:41
rcgldr
15.1k31333
add a comment |
In the <list> header which can be seen in Visual Studio 2017, you will find a function template for _Sort which follows merge sort.
You can find several overloads and function templates for merge function as well.
answered Nov 23 at 4:54
P.W
10.9k3742
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53439338%2fwhat-sorting-algorithm-does-listsort-use-in-msvc%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
The algorithm was changed from bottom up to top down merge sort in Visual Studio 2015. The author of the change stated this was done to handle a list with no default allocator, but that could have been easily handled by using get_allocator() (the fix would include an instance of get_allocator() for each of the 26 elements in the array of lists) when declaring the list.
The author did note that switching to top down meant a performance hit, but correctly pointed out if performance was an issue, then in most cases, moving the list to a vector, sorting the vector, then creating a list from the sorted vector would be faster. Still, most of the STL functions are reasonably optimal, so the argument from some was that the earlier bottom up approach could be fixed to handle a no default allocator list.
Although the author did not mention this, in a discussion in the link below, it was also pointed out that the top down implementation avoided losing data if a user compare function threw an exception. However other STL functions such as std::stable_sort() will lose data if a compare function throws an exception, and my impression is exceptions created by user supplied functions aren't a priority for VS STL and should be caught with debug builds.
`std::list<>::sort()` - why the sudden switch to top-down strategy?
Wiki article includes example for both top down and bottom up merge sort for linked lists:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
answered Nov 23 at 8:41
rcgldr
15.1k31333
add a comment |
The algorithm was changed from bottom up to top down merge sort in Visual Studio 2015. The author of the change stated this was done to handle a list with no default allocator, but that could have been easily handled by using get_allocator() (the fix would include an instance of get_allocator() for each of the 26 elements in the array of lists) when declaring the list.
The author did note that switching to top down meant a performance hit, but correctly pointed out if performance was an issue, then in most cases, moving the list to a vector, sorting the vector, then creating a list from the sorted vector would be faster. Still, most of the STL functions are reasonably optimal, so the argument from some was that the earlier bottom up approach could be fixed to handle a no default allocator list.
Although the author did not mention this, in a discussion in the link below, it was also pointed out that the top down implementation avoided losing data if a user compare function threw an exception. However other STL functions such as std::stable_sort() will lose data if a compare function throws an exception, and my impression is exceptions created by user supplied functions aren't a priority for VS STL and should be caught with debug builds.
`std::list<>::sort()` - why the sudden switch to top-down strategy?
Wiki article includes example for both top down and bottom up merge sort for linked lists:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
answered Nov 23 at 8:41
rcgldr
15.1k31333
add a comment |
The algorithm was changed from bottom up to top down merge sort in Visual Studio 2015. The author of the change stated this was done to handle a list with no default allocator, but that could have been easily handled by using get_allocator() (the fix would include an instance of get_allocator() for each of the 26 elements in the array of lists) when declaring the list.
The author did note that switching to top down meant a performance hit, but correctly pointed out if performance was an issue, then in most cases, moving the list to a vector, sorting the vector, then creating a list from the sorted vector would be faster. Still, most of the STL functions are reasonably optimal, so the argument from some was that the earlier bottom up approach could be fixed to handle a no default allocator list.
Although the author did not mention this, in a discussion in the link below, it was also pointed out that the top down implementation avoided losing data if a user compare function threw an exception. However other STL functions such as std::stable_sort() will lose data if a compare function throws an exception, and my impression is exceptions created by user supplied functions aren't a priority for VS STL and should be caught with debug builds.
`std::list<>::sort()` - why the sudden switch to top-down strategy?
Wiki article includes example for both top down and bottom up merge sort for linked lists:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
answered Nov 23 at 8:41
rcgldr
15.1k31333
The algorithm was changed from bottom up to top down merge sort in Visual Studio 2015. The author of the change stated this was done to handle a list with no default allocator, but that could have been easily handled by using get_allocator() (the fix would include an instance of get_allocator() for each of the 26 elements in the array of lists) when declaring the list.
The author did note that switching to top down meant a performance hit, but correctly pointed out if performance was an issue, then in most cases, moving the list to a vector, sorting the vector, then creating a list from the sorted vector would be faster. Still, most of the STL functions are reasonably optimal, so the argument from some was that the earlier bottom up approach could be fixed to handle a no default allocator list.
Although the author did not mention this, in a discussion in the link below, it was also pointed out that the top down implementation avoided losing data if a user compare function threw an exception. However other STL functions such as std::stable_sort() will lose data if a compare function throws an exception, and my impression is exceptions created by user supplied functions aren't a priority for VS STL and should be caught with debug builds.
`std::list<>::sort()` - why the sudden switch to top-down strategy?
Wiki article includes example for both top down and bottom up merge sort for linked lists:
https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation_using_lists
https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
answered Nov 23 at 8:41
rcgldr
15.1k31333
edited Nov 23 at 9:35
answered Nov 23 at 8:41
rcgldr
15.1k31333
answered Nov 23 at 8:41
rcgldr
15.1k31333
answered Nov 23 at 8:41
rcgldr
15.1k31333
15.1k31333
add a comment |
add a comment |
In the <list> header which can be seen in Visual Studio 2017, you will find a function template for _Sort which follows merge sort.
You can find several overloads and function templates for merge function as well.
answered Nov 23 at 4:54
P.W
10.9k3742
add a comment |
In the <list> header which can be seen in Visual Studio 2017, you will find a function template for _Sort which follows merge sort.
You can find several overloads and function templates for merge function as well.
answered Nov 23 at 4:54
P.W
10.9k3742
add a comment |
In the <list> header which can be seen in Visual Studio 2017, you will find a function template for _Sort which follows merge sort.
You can find several overloads and function templates for merge function as well.
answered Nov 23 at 4:54
P.W
10.9k3742
In the <list> header which can be seen in Visual Studio 2017, you will find a function template for _Sort which follows merge sort.
You can find several overloads and function templates for merge function as well.
answered Nov 23 at 4:54
P.W
10.9k3742
answered Nov 23 at 4:54
P.W
10.9k3742
answered Nov 23 at 4:54
P.W
10.9k3742
answered Nov 23 at 4:54
P.W
10.9k3742
10.9k3742
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53439338%2fwhat-sorting-algorithm-does-listsort-use-in-msvc%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
how about writing a minimal program and stepping-in with the debugger?
– David Haim
Nov 23 at 0:25
I removed the last question which is not related to the title or primary question. Regardless: (specific implementations and variations of) merge sort have a wide spread adoption across most languages as a general sort mechanism because it just "works well in the general case" (it is also a stable sort). A merge sort is even used with 'introsort'.
– user2864740
Nov 23 at 0:27
FWIW: en.wikipedia.org/wiki/Sorting_algorithm
– user2864740
Nov 23 at 0:33
" when I look at the article here" - where?
– Neil Butterworth
Nov 23 at 0:36
1
Implementation is in the list header,
_Sort()function. Have a look. Yes, merge sort in vs2017.– Hans Passant
Nov 23 at 1:17