Merge sort

The maxim “Divide et impera” or divide and conquer took root in the Greek kingdom of Macedon. In times of Philip II of Macedon (359–336 BC) who was the father of Alexander the Great.

philip-ii-of-macedonia

It seems that initially this rule was used in politics, warfare and in tactical maneuvers. But nowadays, we can also meet this principle in economics, computer science, usually we can solve a complex problem using divide and conquer technique. The main idea behind this is to take something big and divide it into small pieces, farther, we can easy work with small piece.

Algotirhm
Recursively or iteratively the unsorted array is divided into two approximately equal sub arrays. Farther, each of these arrays also must be divided into two parts and so on until we get only one element per sub array. Since the array is divided into small pieces, we can merge sub arrays starting from the smallest to the largest, to produce sorted array.
Step-by-step example

I’ve made the diagram bellow. There are eight sheeps on it in unsorted order. Step-by-step these sheeps will be divided and merged. At the end they appear in numeric order. Hope this diagram will help you to understand the algorithm =)

ms_example

Implementation

My implementation can be found on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/sort/MergeSort.java

Complexity

merge_sort_plot

Worst case: O(n log n).

Average case: O(n log n).

Best case: O(n log n).

Conclusion

Merge sort is one of the fastest algorithms. It has O (n log n) complexity which makes it very good for sorting big volumes of data. But its drawback is that unlike quicksort, it requires more extra memory and in practice, quick sort is faster. At the same time merge sort is stable algorithm, so you can use it if stability is mandatory, in other cases quick sort is better.

Quiz

Q: Which general method use the merge sort?
Click here to check your answer.

A: Merge method.

Q: Does merge sort require extra memory?
Click here to check your answer.

A: Yes.

Q: What is the average and worst case of merge sort?
Click here to check your answer.

A: O(n log n).

Q: Does merge sort use comparison?
Click here to check your answer.

A: Yes.

Q: Is merge sort stable sorting algorithm?
Click here to check your answer.

A: Yes.

Leave a Reply