Implementing sort and/or search algorithms - where and why

Question

From time to time have I come across manually implemented sort and/or search algorithms, instead of using language implemented algorithms. Most source code I've been looking into is written in Java, C# or PHP - but I'd guess this phenomenon is language agnostic.

Regarding regular data structures such as lists; Why and where do you implement your own algorithm? Ideological reasons? More memory efficient? Can't stand the idea of using built-in features? Java preferably uses mergesort (in Collections.sort()), which has some overhead when you compare it to quicksort as an example. If you have a favorite which you use on a regular basis for doing common tasks, you're more than welcome to submit it in your language of choice!

Answer 1

• Not every sort algorithm is implemented by the standard library.
• Not every language supports generic data types/containers
• Sometimes you need to switch between sorting algorithms depending on data-size
• Tweaking the algorithm for a particular set of input is easier
• To measure processor speed
• Coursework
• Just for fun

These are just some of the reasons ...

Answer 2

Bogosort:

while (!is_sorted(array)) {
    randomly_shuffle(array);
}

Expected running time: O(n!)

:)

Answer 3

Built in language implementations will be normally be faster, but only if you are sorting/searching in a standard way. As soon as you do anything a little unusual, be it the way the key is interpreted, dealing with multiple pointers, hooking into a different enviroment and so on you can better performance by tweaking the basic routines to match your exact requirements.

For instance, I needed to keep three large (huge) data sets sorted on the same key, so I had to go back to source and alter the C quick sort code to move elements on three distinct arrays of data.

Answer 4

In C++ you can have a container with an array inside that is only searched by methods of the container. You can use some library implementation but then you'll have to provide a comparator class and that's the same amount of code as simply writing a for() loop. Why produce a new entity (comparator class) for such case?