Skip to main content
ICT
Lesson A18 - Merge and MergeSort
 
Main Previous Next
Title Page >  
Summary >  
Lesson A1 >  
Lesson A2 >  
Lesson A3 >  
Lesson A4 >  
Lesson A5 >  
Lesson A6 >  
Lesson A7 >  
Lesson A8 >  
Lesson A9 >  
Lesson A10 >  
Lesson A11 >  
Lesson A12 >  
Lesson A13 >  
Lesson A14 >  
Lesson A15 >  
Lesson A16 >  
Lesson A17 >  
Lesson A18 >  
Lesson A19 >  
Lesson A20 >  
Lesson A21 >  
Lesson A22 >  
Lesson AB23 >  
Lesson AB24 >  
Lesson AB25 >  
Lesson AB26 >  
Lesson AB27 >  
Lesson AB28 >  
Lesson AB29 >  
Lesson AB30 >  
Lesson AB31 >  
Lesson AB32 >  
Lesson AB33 >  
Vocabulary >  
 

C. Recursive MergeSort page 5 of 9

  1. Instead of dividing the list once, a recursive mergeSort will keep dividing the list in half until the sublists are one or two values in length.

  2. When developing a recursive solution, a key step is identifying the base case of the solution. What situation will terminate the recursion? In this case, a sublist of one or two values will be our two base cases.

  3. Let's try and work through the recursive mergeSort of a list of eight values.

The list is divided into two sublists:

Now let's work on the left sublist. It will be divided into lists of two.

Each list of two is now very easy to sort. After each list of two is sorted, we then merge these two lists back into a list of four.

Now the algorithm proceeds to solve the right sublist (positions 5-8) recursively. Then the two lists of four are merged back together.

 

Main Previous Next
Contact
 © ICT 2006, All Rights Reserved.