What sorting algorithm does list::sort use in msvc?












0














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++







share|improve this question




















  • 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
















0














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++







share|improve this question




















  • 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














0












0








0







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++







share|improve this question















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++






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 23 at 0:25









user2864740

43.5k670147




43.5k670147










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














  • 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












2 Answers
2






active

oldest

votes


















2














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






share|improve this answer































    1














    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.






    share|improve this answer





















      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
      });


      }
      });














      draft saved

      draft discarded


















      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









      2














      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






      share|improve this answer




























        2














        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






        share|improve this answer


























          2












          2








          2






          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






          share|improve this answer














          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







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 23 at 9:35

























          answered Nov 23 at 8:41









          rcgldr

          15.1k31333




          15.1k31333

























              1














              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.






              share|improve this answer


























                1














                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.






                share|improve this answer
























                  1












                  1








                  1






                  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.






                  share|improve this answer












                  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.







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered Nov 23 at 4:54









                  P.W

                  10.9k3742




                  10.9k3742






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      -

                      Popular posts from this blog

                      A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

                      Image
                      0 I found a lot of questions abount appendices and ToC. Many users want appendices to be grouped in an Appendix part, however some problems arise with ToC, hyperref, PDF viewer bookmarks, and so on. There are different solutions which require extra packages, command patching and other extra code, however none of them satisfies me. I almost found an easy way to accomplish a good result, where appendices are added to bookmarks in the right way and hyperref links point to the right page. However, the number of the "Appendix" part page is wrong (it's the number of appendix A). Is there any EASY way to fix that? This is a MWE: documentclass{book} usepackage[nottoc,notlot,notlof]{tocbibind} usepackage{hyperref} begin{document} frontmatter tableofcontents mainmatter part{First} chapter{...
                      Read more

                      Calculate evaluation metrics using cross_val_predict sklearn

                      Image
                      1 In the sklearn.model_selection.cross_val_predict page it is stated: Generate cross-validated estimates for each input data point. It is not appropriate to pass these predictions into an evaluation metric. Can someone explain what does it mean? If this gives estimate of Y (y prediction) for every Y (true Y), why can't I calculate metrics such as RMSE or coefficient of determination using these results? python scikit-learn cross-validation share | improve this question edited Nov 28 '18 at 17:52 desertnaut 20.3k 7 43 79 ...
                      Read more

                      Insert data from modal to MySQL (multiple modal on website)

                      Image
                      0 I have problem with inserting data to MySQL from modal. My modal: <a href="#" class="badge badge-pill badge-success">6 komentarzy</a> <a href="#" class="badge badge-pill badge-danger">brak komentarzy</a> <a data-toggle="modal" href="#add_desk_comm_{$desk_['desk_id']}" data-target="#add_desk_comm_{$desk_['desk_id']}" class="ediiit">(dodaj)</a> <div class="modal fade" id="add_desk_comm_{$desk_['desk_id']}" tabindex="-1" role="dialog" aria-labelledby="edit_printer" aria-hidden="true"> <div class="modal-dialog" role="document"> ...
                      Read more