__Sorting Algorithms - Merge Sort__

Merge sort also uses divide and conquer technique for sorting, but unlike
quick sort, it requires some additional memory. It is one of the most
efficient sorting algorithms.

Merge sort divides the sequence in two halves and then treats those two
halves as a sequence and keeps on dividing these sub-sequences in two
halves until we can’t divide them anymore.

Now we will start merging those divided parts in the same order in which
they were separated but, while merging two sub sequences, we will pick the
smallest element available in both sub sequences and place it in the new
subsequence.

This will be done until both sub-sequences are empty which will ensure that
the new subsequence generated after merging these two sub sequences has all
the elements in placed ascending order.

This process of merging sub-sequences will be continued until the
sub-sequence has a length equal to the original sequence.

Unlike quick sort, merge sort requires O(N) extra space while storing the
small sub-sequences.

Worst case time complexity of merge sort is O(n*log(n))

The visualisation of merge sort is as follows:

Implementation of merge sort is as follows:

**Time Complexity : O( n logn ) **

So that’s it for this article we will be coming up with our next article on
further topics very soon till then keep learning, keep coding, keep reading
and keep improving !!

Happy Coding 😊

By Programmers Army