Class 29: More Efficient Sorting Algorithms

Held Friday, October 13, 2000

Summary

Today we visit our first divide-and-conquer sorting algorithm, merge sort.

Notes

• Exam 3 is ready.
• I'll use the last fifteen minutes of today's class for a final pre-break discussion of the project.
• No outline for today yet, sorry. (I'll write it during break.)

Overview

Sorting with Divide and Conquer

• In the previous class, we identified a number of interesting sorting algorithms which took O(n²) time.
• Can we do better? Well, sometimes using divide-and-conquer helps speed up algorithms (in our experience from O(n) to O(log₂n)).
• We'll look at two different ways of ``splitting'' the array.

Merge Sort

• We can develop a number of sorting techniques based on the divide and conquer technique. One of the most straightforward is merge sort.
• In merge sort, you split the list, array, collection or ... into two parts, sort each part, and then merge them together.
• Unlike the previous algorithms, merge sort requires extra space for the sorted arrays or subarrays.
• We'll write this as a non-inplace routine which returns a new, sorted array, rather than sorting the existing array.

Running Time

• What is the running time?
• We can use recurrence relations:
  • Let f(n) be the running time of merge sort on input of size n.
  • f(1) = 1
  • f(n) = n + 2*f(n/2)
• Let's run this for a few steps
  • f(n)
  • = n + 2*f(n/2)
  • = n + 2*f(n/2)
  • = n + 2*(n/2 + 2*f(n/2/2))
  • = n + n + 4*f(n/4)
  • = n + n + 4*(n/4 + 2*f(n/4/2))
  • = n + n + n + 8*f(n/8)
• Generalizing
  • f(n) = kn + 2^k*f(n/2^k)
• When k = log₂n
  • f(n) = nlog₂n + n*1
• Therefore, f(n) is in O(nlog₂n).

Running Time, Revisited

• We can also use a somewhat nontraditional analysis technique.
• Assume that we're dealing with n = 2^x for some x.
• Consider all the sorts of Arrays of size k as the same "level".
• There are n/k Arrays of size k.
• Because we divide in half each time, there are log_2(n) levels.
• Going from level k to level k+1, we do O(n) work to merge.
• So, the running time is O(n*log_2(n)).

A Problem

• Unfortunately, merge sort requires significantly more memory than do the other sorting routines (you can spend some time trying to come up with an ``in place'' merge sort, but you are quite likely to fail).

Other Versions

• We've written merge sort so that it does not affect the original array.
• How might we write it so that it creates a sorted array?
  • Will that save space?

Splitting via Size

• Suppose we split the array into small and large elements.
• How does that affect everything?
• Think about it.