10.2. Recursive Searching and Sorting

In Unit 7, we learned about searching and sorting algorithms using iteration (loops) to search or sort arrays and ArrayLists. In this lesson, we will take a look at a recursive binary search algorithm and a recursive merge-sort algorithm.

10.2.2. Merge Sort

In Unit 7, we looked at two sorting algorithms, Selection Sort and Insertion Sort. In this lesson, we will look at a third sorting algorithm, Merge Sort, which uses recursion. Merge Sort is actually more efficient (faster) than Selection Sort and Insertion Sort because it divides the problem in half each time like binary search. This is called a divide and conquer algorithm.

A merge sort recursively breaks the values to be sorted in half until there is only one value to be sorted and then it merges the two sorted lists into one sorted list. The code shown below uses a second array the same size as the original array for merging the values in order. Then it copies all of the sorted values back into the original array.

Here is a folk dance video that shows the merge sort process.

And here is a short video that describes how merge sort works.

The code for mergeSort below is from the AP CS A course description.

To identify a merge sort look for the following:

  • 3 methods, mergeSort, mergeSortHelper, and merge

  • mergeSortHelper is recursive

You can see this executing using the Java visualizer for merge sort.

You can trace through a merge sort algorithm given an array by using parentheses or curly brackets to show how the array is divided into subarrays and then merged. For example, here is how you could write down the trace of mergeSort(arr1) where arr1 = {86, 3, 43, 5} like in the example above.

  1. Split 1: { {86, 3} , {43, 5} }

  2. Split 2: { { {86},{3}} , { {43},{5}} }

  3. Merge 1: { {3, 86} , {5,43} }

  4. Merge 2: { 3, 5, 43, 86 }

exercise Check Your Understanding

    10-2-3: Under what condition will a merge sort execute faster?

  • If the data is already sorted in ascending order
  • This won't really affect the execution time for merge sort.
  • If the data is already sorted in descending order
  • This won't really affect the execution time for merge sort.
  • It will always take the same amount of time to execute
  • It will take about the same time regardless of the data.

    10-2-4: Which sort should be the fastest most of the time?

  • selection sort
  • Merge sort is always faster than selection sort.
  • insertion sort
  • Merge sort is usually faster than insertion sort.
  • merge sort
  • Merge sort is always faster than selection sort and usually faster than insertion sort.

10.2.3. groupwork Tracing Challenge : Recursive Search and Sort

Working in pairs, practice the recursive binary search and merge sort algorithms with a deck of cards or pieces of paper with numbers or names on them. Here’s a video that shows merge sort with cards.

Work in pairs to do the following tracing problems.

10-2-5: Trace through mergeSort(array) where array = {5, 2, 20, 22, 17, 15, 8, 10} writing down each split and merge.

10.2.4. Summary

  • The binary search algorithm can be written either iteratively or recursively.

  • Data must be in sorted order to use the binary search algorithm.

  • The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in until the desired value is found or all elements have been eliminated.

  • Binary search can be more efficient than sequential/linear search.

  • Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.

You have attempted of activities on this page
Next Section - 10.3. Recursion Summary