13.6. Merge SortΒΆ

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.

To identify a merge sort look for the following:

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

To see this executing using the Java Visualizer click on the following Merge-Sort

    12-6-1: 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.
    12-6-2: Which sort should be the fastest most of the time?
  • selection sort
  • Selection sort always takes about the same time. Merge sort is always more effecient 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.
Next Section - 13.7. Easy Multiple Choice Questions