Merge Sort vs Insertion Sort

What’s better? Time and space complexity wise.

This past week, I dived into sorting algorithms and tackled different problems to see which algorithm works best for which kind of problem. Time and again, I found myself contemplating between two common sorting algorithms: merge sort and insertion sort. Although different, many times it was hard for me to choose which algorithm will suit a specific problem better. Hence, in this article we will take a deeper dive into each and conclude which algorithm works best based on different cases.

What is Merge Sort?

Merge sort is an external algorithm based on the divide and conquer strategy. In this sorting algorithm:

• The initial elements are first split into two sub-arrays (n/2) repeatedly until only one element is left
• Merge sort uses additional storage for sorting the arrays
• Merge sort uses three arrays in total: where two are used for storing each half and the third external one is used to store the final sorted list by merging the other two and each array is then sorted recursively
• At the end, all the sub-arrays are merged to make it ’n’ element size of the array.

What is Insertion Sort?

Insertion sort is a sorting algorithm in which elements are firstly taken from an unsorted item, inserting it in sorted order in front of the other items and repairing until all items are in order. This algorithm is simple to implement and usually consists of two loops: an outer loop to pick the items and an inner loop to iterate through the array.

Key differences

1. Time complexity: In merge sort the worst case is O(n log n); average case is O(n log n); best case is O(n log n) whereas in insertion sort the worst case is O(n2); average case is O(n2); best case is O(n).
2. Space Complexity: Merge sort, being recursive takes up the space complexity of O(n) hence it cannot be preferred over the place where memory is a problem. However, insertion sort only takes up O(1) space complexity. It sorts the entire array by using one extra variable.
3. Datasets: Merge sort is definitely preferred for huge data sets. This is because it happens to compare all the elements present in the array hence is not much helpful for small datasets. Insertion sort however, is the go-to for fewer elements. It becomes fast when data is already sorted or nearly sorted because by default, it skips the sorted values.
4. Efficiency: Considering the average time complexity of both algorithms, we can safely say the merge sort is efficient in terms of time and insertion sort is efficient in terms of space.
5. Sorting Method: Merge sort is an external sorting method in which the data that is to be sorted cannot be accommodate in memory and needs ‘auxiliary’ memory for sorting whereas insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position (the position to which is belongs in a sorted array).
6. Stability: Merge sort is stable as two elements with equal value appear in the same order in a sorted output as they were in the input unsorted array, whereas insertion sort take O(n2) time on both data structures (array and linked list). All in all, there probably isn’t that much of a time difference between both data structures.

In conclusion, some situations (depending on the input data structure, if it is already nearly sorted and the size of the input) merge sort or insertion sort can be of different value.