# DS&A

Data Structures and Algorithms

## Recursive Sorting

Apr 162018

In the previous post we saw two iterative sorting algorithms: selection sort and insertion sort both work using a loop to put the right values in the right places, one at a time. They are two of the simplest sorting algorithms. But they’re not very efficient — for long lists, they’re too slow.﻿(1)

In this post we’ll see one of the simplest efficient sorting algorithms, called merge sort. Rather than sorting items one-by-one, it works by recursively sorting shorter lists.

The strategy is:

1. Split the list data apart into two shorter lists,
2. Sort the shorter lists,
3. Put the data back together into one sorted list.

Step 2 is free — we just make a recursive call on each of the shorter lists. The hard work will either be in step 1 or step 3 — we must do some sorting either when we split the data apart, or when we put it back together again. Merge sort does the hard work in step 3.﻿(2)

### Merge sort

The merge sort algorithm begins by splitting the list into a first half and a second half. Both halves are sorted recursively; the hard work happens when we merge them back together. Try it out with the model below:

(This interactive feature requires Javascript to be enabled in your browser.)

After splitting the list in two, we can make a “leap of faith” by trusting that the recursive calls will sort the shorter lists correctly.

Once both halves are sorted, we need to merge them back together; this is a subproblem. To build the output list, one value at a time, we must choose the smallest remaining value from one of the two halves. Since both halves are sorted, the smallest remaining value in each half is the first unused one.﻿(3)

The algorithm sorts the output into a new list, so it is an “out-of-place” sort. Here’s an implementation in Python:

``````def merge_sort(lst):
# if the list is this short, no sorting is necessary
if len(lst) <= 1:
# return a copy, out-of-place
return list(lst)

# half the length, rounded down
m = len(lst) // 2

# list slicing
A = lst[:m]
B = lst[m:]

# sort both halves recursively
A = merge_sort(A)
B = merge_sort(B)

return linear_merge(A, B)

def linear_merge(A, B):
# merge two sorted lists
output = []
i, j = 0, 0

while i + j < len(A) + len(B):
if i < len(A) and (j == len(B) or A[i] <= B[j]):
output.append(A[i])
i += 1
else:
output.append(B[j])
j += 1

return output``````

#### Footnotes

1. We’ll do a proper analysis later.
2. Another efficient recursive sorting algorithm, quicksort, does the hard work in step 1 instead.
3. This solution is called a linear merge, hence the name merge sort.

## New comment

Your comment will not appear until a moderator approves it.

Atom

hosted on werp.site