Define Merge sort & find the time complexity for it?

Merge Sort

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:

1. Divide Step

If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A₁ and A₂, each containing about half of the elements of A.

2. Recursion Step

Recursively sort array A₁ and A₂.

3. Conquer Step

Combine the elements back in A by merging the sorted arrays A₁ and A₂ into a sorted sequence.

We can visualize Merge-sort by means of binary tree where each node of the tree represents a recursive call and each external nodes represent individual elements of given array A. Such a tree is called Merge-sort tree. The heart of the Merge-sort algorithm is conquer step, which merge two sorted sequences into a single sorted sequence.

To begin, suppose that we have two sorted arrays  A₁[1], A₁[2], . . , A₁[M] and A₂[1], A₂[2], . . . , A₂[N]. The following is a direct algorithm of the obvious strategy of successively choosing the smallest remaining elements from A₁ to A₂ and putting it in A.

MERGE (A₁, A₂, A)

i.← j 1
A₁[m+1], A₂[n+1] ← INT_MAX
For k ←1 to m + n do
    if A₁[i] < A₂[j]
        then A[k] ← A₁[i]
            i ← i +1
        else
            A[k] ← A₂[j]
                j ← j + 1

Merge Sort Algorithm

 MERGE_SORT (A)

A₁[1 . . [n/2]] ← A[1 . . [n/2]]
A₂[1 . . [n/2]] ← A[1 + [n/2] . . n]
Merge Sort (A₁)
Merge Sort (A₁)
Merge Sort (A₁, A₂, A)

Analysis

Let T(n) be the time taken by this algorithm to sort an array of n elements dividing A into subarrays A₁ and A₂ takes linear time. It is easy to see that the Merge (A₁, A₂, A) also takes the linear time. Consequently,

T(n) = T([n/2]) + T([n/2]) + θ(n)

for simplicity

T(n) = 2T (n/2) + θ(n)

The total running time of Merge sort algorithm is O(n lg n), which is asymptotically optimal like Heap sort, Merge sort has a guaranteed n lg n running time. Merge sort required  (Theta(n)) extra space. Merge is not in-place algorithm. The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program.