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:
- The sequence is split till every subsequence has at most one element.
- 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 ...
Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
