Mergesort in C++

Standard

This is my favorite sorting algorithm. It’s easy and it also can be parallelized using multiple machines / processes for huuuuge data sets.

Its runtime is (like Quicksort) O(n log(n)). Again here it’s because you split each part into two and work on it recursively.

Most fun is to think about the way Mergesort works in general and find your own implementation. Well, of course each implementation will look pretty much the same in the end…

Quicksort implementation in C++

Standard

This one among a thousand implementaions of the Quicksort algorithm.

Its runtime is O(n log(n)) since you divide each part into two and recursively sort the two parts (always splitting by 2 is logarithmic growth…).

You could optimize it by using Insertionsort for a small input vector (i.e. less than 50 elements). Additionally you can convert the recursive algorithm into a iterative one (maybe I will post this in the future).
You should be careful, and always pass the input vector per reference “&”. If you don’t sorting does not take effect on the input in the end.

Here is another implementation that works on plain integer arrays.