The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Sorting

Problem :-
Implement the Merge sort algorithm.

Solution :-
Merge sort is a divide & conquer algorithm which works by dividing the array of elements into sub-arrays, sorting the subarrays and then merging the sorted sub-arrays to produce final sorted array.
Consider an unsorted array of size n. First the unsorted array is divided into n sub-arrays ( each array of size 1 ) [ an array of size 1 is by default sorted ].
Merge the two adjacent sorted sub-arrays and repeat the steps of sorting & merging sub-arrays until only one sub-array remains and that is the final sorted array. Complexity of the algorithm is O(n log n).
Consider the following array { 7, 2, 5, 3, 1, 8, 4, 6 }. Let's see how Merge sort technique works :-

{ 7 } | { 2 } | { 5 } | { 3 } | { 1 } | { 8 } | { 4 } | { 6 } ( Array is divided into 8 sub-arrays of size 1 )

First Merge :-
{ 2, 7 } | { 3, 5 } | { 1, 8 } | { 4, 6 } ( Merge the adjacent sorted sub-arrays of size 1 )

Second Merge :-
{ 2, 3, 5, 7 } | { 1, 4, 6, 8 } ( Merge the adjacent sorted sub-arrays of size 2 )

Third Merge :-
{ 1, 2, 3, 4, 5, 6, 7, 8 } ( Merge the adjacent sorted sub-arrays of size 4 )

Now, we have only one sub-array of size n, which is the final sorted array.