How are there so many sorting algorithms?

[Avichal]

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?

 

[voko]

Unless you specify some strict criteria for admissible sorting algorithms, there are infinitely many of them.

 

[jtbell]

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.

 

[rcgldr]

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.

 

[Avichal]

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?

 

[voko]

I'm asking whether there is a limit to number of algorithms to such a simple problem?

You were given an answer to this.

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

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.

 

[Avichal]

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.

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.

 

[nevere]

their is a 4 volume book called The art of algorithms, flip through it sometime.

 

[nevere]

The Art of Computer Programming I mean,lol

 

[Borg]

Perhaps a visualization will help.

https://www.youtube.com/watch?v=kPRA0W1kECg

 

[Avichal]

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