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.

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.

1 / 1

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

Merging Two Sorted Arrays

1 / 1

Merging two arrays into a new array (see lecture video for explanation).

Find Middle and Dividing a Linked List

1 / 1

To find the middle and subdivide a linked list, use two iterators. Let pMid move once for every two moves of pCurr.

Merging Two Sorted Linked Lists

Sorted sub-lists are merged into one sorted list.

• Compare elements of sub-lists

• Adjust pointers of nodes with the smaller datum.

1 / 1

Merging two sorted link list into one (see lecture video for explanation).

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 of Sorting Algorithms

• 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 and Midterm Exam Preparation

After studying this material, complete Lab 11.

Also, review the Midterm Study Guide and complete the practice problem so you know you understand how to prepare. Ask your instructor any questions you may have well before the exam.