How to implement Merge sort ?

Merge sort - O(n log n)

• Divide and Conquer
• Divide into 2 parts
• Divide each part into 2 sub-parts recursively
• Merge parts in reverse order
• 
  
• Example
• Divide array of 8 numbers to 2 sub arrays
• Divide each subarray again into 2 (4 sub arrays)
• Divide each subarray again into 2 (8 sub arrays)
• Merge into 4 subarrays
• Merge into 2 subarrays
• Merge into 1 array

27 10 12 25 34 16 15 31

27  10  12   25   | 34   16  15  31

27  10 | 12   25   | 34   16  | 15  31

-------------------------------------------------------
27 | 10 | 12 | 25 | 34 | 16 | 15 | 31
-------------------------------------------------------
10 27 | 12 25 | 16 34 | 15 31
10 12 27 25 | 15 16 31 34
10 12 15 16 25 27 31 34