Merge sort uses the divide and conquer philosophy. There will be a function split that will split a sequential data structure into two parts in such a way that the number of elements in the two split parts will differ by one element at the maximum. The split daughter lists, after merging, return the permutation of the original list.
Merge sort steps can be laid out in the following fashion:
No worries, we will discuss all the steps in detail in the following pages. Let's start with the split.
The following diagram explains the splitting of a sequence:
We start our sequence ...