Fun with Sorting

Student Worksheet:
Session 1 – Insertion Sort

This is a group exercise. Before starting, please form a group of 3-5 students.

 Single Insertion

Draw up 8 cards, each with a different number. Have one student in your group be the controller, and the others should play along. Only the controller is allowed to see the numbers.

The controller should set up the cards for Single Insertion, and the others should play to sort the list. Do this at least 5 times, and fill up the table below.

Round	Number of yes/no questions asked	What was the out-of-place number?	
1			
2			
3			
4			
5			

Based on the information you entered above, answer the following questions:

1.	What is the average number of questions asked in one round?

______________________

2.	Assume that you were to fill up the table above for 5000 Single Insertions. What do you think would be the largest possible value in the second column (The number of yes/no questions asked)?

______________________

3.	Assume that you were working with a list of 10 numbers instead of 8. What would be your answer to Question 2 in that case?

______________________

4.	Can you now relate the size of the list to the number of questions asked in the worst case? Give a very brief answer about how you think the size of the list and the questions asked in the worst case (Remember, the fewer the number of questions, the better. So when we say “worst case”, we mean the largest possible number of questions asked)

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

 
 Insertion Sort

Now, with those same cards, play the Insertion Sort game. Remember to start off with a completely random list.

Do Insertion Sort at least 5 times, and fill out the table below. The controller should keep a record of the third column before starting the sorting, and reveal it after the list has been sorted.

Round	Number of yes/no questions asked	What was the starting list?	
1			
2			
3			
4			
5			

Based on the information you entered above, answer the following questions:

1.	What is the average number of questions asked in one round?

______________________

2.	You must have realized that Insertion Sort is just a series of Single Insertions. Give a very brief answer about how you would relate the number of Single Insertions with the size of the list to be sorted.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

3.	Remember your answer to Question 2 from the Single Insertion exercise. Use that answer to calculate the number of questions you would need to ask in Insertion Sort in the “worst case”. Show your steps.

Final Answer: __________________

4.	Go head-to-head with another group in a sorting match to see who can sort a randomized list faster. There will be one controller from each team, in the interest of fairness. The game rules should be strictly followed, but you may use any procedure you want. 

Number of questions you asked: _______________________

Number of questions your opponent asked: _______________________

Did you win? _______________________
 
      Fun with Sorting

Student Worksheet:
Session 2 – Merge Sort

This is a group exercise. Before starting, please form a group of 3-5 students.

 Two-List Merge

Draw up 8 cards, each with a different number. Have one student in your group be the controller, and the others should play along. Only the controller is allowed to see the numbers.

The controller should set up the cards for Two-list Merge, and the others should play to sort the list. Do this at least 5 times, and fill up the table below.

Round	Number of yes/no questions asked	What was the starting list?	
1			
2			
3			
4			
5			

Based on the information you entered above, answer the following questions:

1.	What is the average number of questions asked in one round?

______________________

2.	Assume that you were to fill up the table above for 5000 Two-list Merges. What do you think would be the largest possible value in the second column (The number of yes/no questions asked)? 

______________________

3.	Assume that you were working with a list of 10 numbers instead of 8. What would be your answer to Question 2 in that case?

______________________

4.	Now go back and have a look at the answers you gave for the exercise on Single Insertion. What similarities do you see? What differences? How do the numbers vary? Do they vary a little, or do they vary a lot? Write down your thoughts on this.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

 Merge Sort

Now, with those same cards, play the Merge Sort game. Remember to start off with a completely random list.

Do Merge Sort at least 5 times, and fill out the table below. The controller should keep a record of the third column before starting the sorting, and reveal it after the list has been sorted.

Round	Number of yes/no questions asked	What was the starting list?	
1			
2			
3			
4			
5			

Based on the information you entered above, answer the following questions:

1.	What is the average number of questions asked in one round?

______________________

2.	You must have realized that Merge Sort is just a series of Two-list Merges. How many Two-list Merges did you do to Merge Sort the list of 8 numbers?

______________________

3.	Remember your answer to Question 2 from the Two-list Merge exercise. Use that answer to calculate the number of questions you would need to ask in Merge Sort in the “worst case”. Show your steps.

Final Answer: __________________

4.	Go head-to-head with another group in a sorting match to see who can sort a randomized list faster. There will be one controller from each team, in the interest of fairness. The game rules should be strictly followed, but you may use any procedure you want.

Number of questions you asked: _______________________

Number of questions your opponent asked: _______________________

Did you win? _______________________