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

###### 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 =)

###### 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

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.

Q: Does merge sort require extra memory?

Click here to check your answer.

Q: What is the average and worst case of merge sort?

Click here to check your answer.

Q: Does merge sort use comparison?

Click here to check your answer.

Q: Is merge sort stable sorting algorithm?

Click here to check your answer.