Divide into two arrays and then sort and merge.

Divide Recursively until Base Case In Recursion i.e only single element is reached as one element is always sorted.
when two individually divided arrays are sorted we can Merge two sorted arrays Time Complexity:
n level tree would be formed
each at each level the tree divides into two parts so 2^x=n ⇒ log2n (height of tree )
Time taken to merge two sorted arrays :O(n)
Time taken for dividing: O(NlogN) :
- N: number of blocks
- logN: height of tree
Total: O(nlogn)

Code

Tags::

Back-links::

Foot-notes::

‧͙⁺˚･༓☾🐺☽༓･˚⁺‧͙