Merge sort is classic example of divide and conquer algorithm approach.

Divide and Conquer Algorithm Design approach: The idea is simple, as the term suggest, we try to divide the original problem into multiple smaller problems. These small problems are solved and the solutions then are merged into one final solution.

The concept is used in merge sorting. Input to any sorting algorithm is a random list (array). For sake of this example let’s take a random array of numbers as input.

Divide Phase: Divide the main array into smaller arrays upto a level that it can sorted easily.

Conquer: Merge these entire sorted arrays into the final solution array.

Example – Lets say we have an array

Original: 99, 23, 45, 12, 67, 28, 09, 98, 44, 84

Divide Phase

Arr1: 99, 23, 45, 12, 67                | Arr2:   28, 09, 98, 44, 84

99, 23, 45                    | 12, 67        |28, 09, 98              | 44, 84

99, 23        | 45           |12    | 67     |28, 09        | 98      |44     | 84

99   | 23   | 45           |12    | 67       |28    | 09   | 98      |44     | 84

Merge Phase

23, 99      | 45           |12, 67            |09, 28   | 98           | 44, 84

23, 45, 99                  | 12, 67          | 09, 28, 98              |   44, 84

12, 23, 45, 67, 99                            | 09, 28, 44, 84, 98

09, 12, 23, 28, 44, 45, 67, 84, 98, 99

Complexity Analysis

The Divide phase of merge sort will need log N operations as in every step we are reducing length of array by half.

Merge step will again have log N merges and in each merge step we will have maximum N comparison, so the overall complexity will (N log N)