Merge Sort Analysis

Conception

The main conception of merge sort is divide and conquer.

Divide

Division aims at dividing the array into separated one using binary method.

Thinking about a binary tree, when the array is divided to a binary tree, it will use combination routine to reform the array from the bottom. Using recursion will achieve this goal, and the when the function stack return, it will call combination every time.

Conquer

When division is finished, it should be able to call combination, and the sorting process will be in the combination routine.

Firstly, the combination should provide space for Left section and Right section, so that it will be able to pick up any value for the sorting process.

Secondly, as said in the above step, each time we watch two subarray to pick up value to store in the original array.

Analysis

Think about that each level that compare ((n/x)*x), n is the number of nodes, x is how many sections that comprise the level. so all of different levels’ total cost is (lg n + 1) * n, so it’s (n * lg n).