Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How are there so many sorting algorithms?

  1. Nov 1, 2013 #1
    I was looking through the list of sorting algorithms and there are so many of them! A simple problem where each element is less that or greater than the next term has so many solutions. How is that?

    My question is a rhetorical one but is there any limit to number of different techniques for sorting?
    Till now the algorithms I have read do the following:-
    Selection sort: Finds the minimum and places in the first position and so on
    Heap sort: Finds the minimum but in an efficient way using binary trees
    Quick sort and Merge sort: Use divide and conquer
    Insertion sort: Finds the correct position and places element there

    Surely there is a limit to number of different techniques for sorting, right?
  2. jcsd
  3. Nov 1, 2013 #2
    Unless you specify some strict criteria for admissible sorting algorithms, there are infinitely many of them.
  4. Nov 1, 2013 #3


    User Avatar

    Staff: Mentor

    We study so many different sorting algorithms because they have different combinations of advantages and disadvantages, which often depend on the kind of data being sorted.
  5. Nov 1, 2013 #4


    User Avatar
    Homework Helper

    Some of the sort algorithms were developed before similar but faster algorithms were discovered, and some are mostly educational and don't offer any significant advantages. As an example of the latter, top down merge sort recursively splits an array into two until repeated recursion produces arrays of size 1, by generating indices stored on the stack during recursion, at which point the merge process begins and flows back up the call chain. Bottom up merge sort skips the unneeded recursive process and just starts off by considering an array of size n to be n arrays of size 1, and uses iteration to generate indices as needed during the merge process.

    The most common sort algorithms found in compiler libraries are variations of quick sort and merge sort. Microsoft / HP C++ Standard Template Library uses quick sort for array / vector types if the original order for equal elements does not need to be preserved called std::sort(), and merge sort if the original order needs to be preserved called std::stable_sort(), and also uses merge sort and an array of list structures (the head and tail pointers) for sorting linked lists called std::list::sort().

    Non-comparason sorts like radix sort are fastest if sorting a large array of 4 to 16 byte integers or something similar where the length of the data that determines the sort order is relatively small.
  6. Nov 1, 2013 #5
    I am not asking why we have so many sorting algorithms.
    I'm asking whether there is a limit to number of algorithms to such a simple problem?

    I guess my question can be generalized as follows:- Given a problem, is there a limit to number of algorithms to the problem.

    While for a complicated problem, there might be infinitely many solutions but in this case i.e. sorting is there a limit? What else can you do to sort apart from the known algorithms?
  7. Nov 1, 2013 #6
    You were given an answer to this.

    Obviously not. If you have an algorithm that produces at least one bit, you can add a step that flips that bit, and another step that flips it back. The result is the same as in the original algorithm. You can add infinitely many steps like that, getting infinitely many algorithms.
  8. Nov 1, 2013 #7
    Ah, I didn't think this in such detail. Probably I should ask whether there are infinitely many ideas or techniques to sort? Anyways, I guess there are indeed infinitely many ways to sort.
    Also since there is no way to count number of solutions to a problem, the question is meaningless.
  9. Nov 13, 2013 #8
    their is a 4 volume book called The art of algorithms, flip through it sometime.
  10. Nov 13, 2013 #9
    The Art of Computer Programming I mean,lol
  11. Nov 15, 2013 #10


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    Perhaps a visualization will help.

  12. Nov 15, 2013 #11
    Cool video!
    Anyways I don't have any trouble understanding the algorithms. I was only interested if there is a limit to the number of algorithms
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook