11.2. Recursive Searching and Sorting

In Unit 8, 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.

11.2.2. Merge Sort

In Unit 8, 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.

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

11.2.3. groupwork Tracing Challenge : Recursive Search and Sort

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.

Do the following tracing problems.

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

11.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