Merge Sort

Merge Sort

Merge sort follows the divide and conquer paradigm.

For mergesort

1. We break the array into two subarrays to be sorted and then combine the ordered subarrays to make the whole ordered array;
2. We do the two recursive calls before working on the whole array;
3. The array is divided in half;

Pros

1. Mergesort guarantees to sort an array of N items in time proportional to N log N, no matter what the input.

Cons

1. Its prime disadvantage is that it uses extra space proportional to N.

https://github.com/explorer436/programming-playground/blob/main/java-playground/my-java-solutions/src/main/java/com/my/company/sorting/algorithms/MergeSort.java