####**MERGE\_SORT** :: Sorts the elements of ```array``` between ```start_index``` and ```final_index```, both inclussively

```
MERGE_SORT(array, start_index, final_index):
	IF start_index < final_index:
		middle_index = FLOOR((start_index + final_index)/2)
		MERGE_SORT(array, start_index, middle_index)
		MERGE_SORT(array, middle_index + 1, final_index)
		MERGE(array, start_index, middle_index, final_index)
```

_Find the middle index._
_Distribute the sorting procedures in two smaller subset of arrays._
_Once those two subset of arrays has been sorted, merge them to obtain the final set of sorted array._


####**MERGE** :: Merges two array in sorted order.
The elements from ```start_index``` till ```middle_index``` is considered as _first array_ while the remaining i.e. the elements from ```middle_index + 1``` (**next to middle**), till ```final_index``` is considered as _Second array_

```
MERGE(array, start_index, middle_index, final_index):
	n1 = middle_index - start_index + 1	//size of first array
	n2 = final_index - middle_index		//size of second array

	//separate the arrays for easier comparison
	FOR i = 1 TO n1:
		FIRST_ARRAY = array[start_index + i - 1]
	FOR j = 1 TO n2:
		SECOND_ARRAY = array[middle_index +j]

	// set the last elements to extremely high value.
	// in case the elements of that array expires, the value of other array elements will always be smaller to this value.
	// this value is also known by sentinal element.
	FIRST_ARRAY[n1 + 1] = INFINITY
	SECOND_ARRAY[n2 + 1] = INFINITY

	i = 1	// keep track of FIRST_ARRAY
	j = 1	// keep track of SECOND_ARRAY

	FOR k = start_index TO final_index
		IF FIRST_ARRAY[i] <= SECOND_ARRAY[j]
			array[k] = FIRST_ARRAY[i]
			i = i + 1
		ELSE
			array[k] = SECOND_ARRAY[j]
			j = j + 1
```

_Divide array (portion we are dealing with) in two separate arrays (first two FOR loops)._
_Take two variables that points to the first element of each array (new ones)._
_Compare the elements pointed by two pointers. Insert the smaller one into the array (old one) and increment its pointer such that it can point to next element in the array (refer to algorithm for MERGE, last FOR loop)._
_The array ultimately obtained has the merged result of first and second array in sorted order._

- **Best Case:** _O(n log(n))_
- **Average Case:** _O(n log(n))_
- **Worst Case:** _O(n log(n))_