Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements recursively, hence consuming less time.

Merge sort runs in O(n*log n) time in all the cases. Two functions are involved in this algorithm. The merge() function is used for the merging two halves and the mergesort() function recursively calls itself to divide the array until the size becomes one.

Use the array below to perform a Merge Sort. Show all necessary workings.

{75, 22, 65, 97, 35, 56, 18, 89}