Sorting Algorithm Comparison

Sorting is one of the most important algorithms that pave way for other algorithms to work. Although in more complex algorithms we use language provided sorting functions, it is important to know how each of the sorting mechanisms work.

When we talk about sorting there are several sorting algorithms developers should be familiar with. Namely

Selection sort
Bubble sort
Insertion sort
Merge sort
Quick sort
Heap sort
Counting sort
Radix sort
Bucket sort

When comparing algorithms we can think of the following factors.

1. Number of swaps

This means how many times elements are being swapped

2. Use of recursion

This means if the algorithm is using recursive calls (calls to the same function within the same function). Recursion algorithms use stack heavily, so it affects the performance.

3. Number of comparisons

This means how many instances of comparison between two elements occur in the algorithm.

4. Amount of extra space required

This means if the algorithms use extra memory or not. Some algorithms use in place operations, meaning they move elements instead of creating new structures. Some algorithms create new structures to sort which requires more free memory to be available.

5. Stable vs Unstable

This means if the algorithm is capable of maintaining relative order of equal elements.

Let's compare the following sorting algorithms.

Algorithm	Recursion	Time Complexity	Space Complexity
Insertion	No	O(n) -> O(n*n)	O(1)