Merge sort

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:

1. The sequence is split till every subsequence has at most one element.
2. Every subsequence is merged in such a way that the merged sequence is sorted too.

No worries, we will discuss all the steps in detail in the following pages. Let's start with the split.

Splitting the sequence

The following diagram explains the splitting of a sequence:

We start our sequence as [1, 3, 5, 2, 6]. In order to split it into two parts, we will fetch two elements (they are 1 and 3 for us) and put them as two subsequences, ss1 and ss2, respectively. Similarly, the next time, 5 and 2 will be taken and added to...