O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required