Merge Sort

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

• In Merge Sort, the given unsorted array with n elements, is divided into n subarrays, each having one element, because a single element is always sorted in itself. 

• Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced.

The concept of Divide and Conquer involves three steps:

• Divide the problem into multiple small problems.

• Conquer the subproblems by solving them. The idea is to break down the problem into atomic subproblems, where they are actually solved.

• Combine the solutions of the subproblems to find the solution of the actual problem.

Example:

Time Complexities:

• Worst Case Complexity: O(n log(n))
  If we want to sort in ascending order and the array is in descending order then, the worst case occurs.

• Best Case Complexity: O(n log(n))
  It occurs when the array is already sorted

• Average Case Complexity: O(n log(n))
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending)