Merge Sort

Chapter 18

Introduction

• Quick Sort: average case; worst case

• Merge Sort: always

• Unlike Quick Sort, it divides the list into two sub-lists of nearly equal size.

• Uses the divide-and-conquer technique.

  • Partitions the list into two sub-lists of nearly equal size.

  • Sorts the sub-lists.

  • Combines the sub-lists into one sorted list.

Merge Sort Algorithm

• Uses recursion.

• If the list is of assize greater than 1,

  1. Divide the list into two sub-lists.

  2. Merge sort the first sub-list.

  3. Merge sort the second sub-list.

  4. Merge the first sub-list and the second sub-list.

Example of how values will divided repeatedly into smaller lists and then merged back together in sorted order.

1 / 1

Merging Two Sorted Arrays

See the lecture video above for the example of merging two arrays.

Find Middle and Dividing a Linked List

1 / 1

Merging Two Linked Lists

Sorted sub-lists are merged into one sorted list.

• Compare elements of sub-lists

• Adjust pointers of nodes with the smaller datum.

See the lecture video above for merging two sorted link list into one.

Analysis: Merge Sort

• Suppose that is a list of elements, with .

• Suppose that is a power of ; that is, for some integer , so that we can divide the list into two sub-lists, each of size:

  will be the number of recursion levels.

Number of elements per recursive level of the Merge Sort

Number of elements per recursive level of the Merge Sort

• To merge two sorted lists of size and , the maximum number of comparisons is .

• Merging two sorted lists into a sorted list is where the actual comparisons and assignments are done.

• Max. # of comparisons at level of recursion:

• There are at most comparisons per recursion level.

• Therefore, there are total comparisons,
  where is the number of levels of recursion.

• Thus, .

• Key comparisons in the worst case:

• Key comparisons in average case:

Summary

• Check out this Sorting Algorithms Animation.

• By asymptotic, we mean the rate of growth of function as grows towards infinity.

• On average, a sequential search searches half the list and makes comparisons, which is inefficient.

• The binary-search algorithm is the optimal worst-case algorithm for solving search problems by using the comparison method.

• A binary search requires the list to be sorted but takes only or O key comparisons.

• Bubble Sort: key comparisons and item assignments.

• Selection Sort: key comparisons and item assignments.

• Insertion Sort: key comparisons and item assignments.

• Both the Quick Sort and Merge Sort algorithms partition a list to sort it.

  • Quick Sort: average number of key comparisons is ; worst case number of key comparisons is

  • Merge Sort: the number of key comparisons is on average and in the worst case.

Lab 11: Insertion, Quick, and Merge Sort

Let’s take a look at Lab 11.