Mergesort Variants
Assignment 5
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Manual Sorting (10 points)
Manually sort the array {S, O, M, E, S, I, M, P, L, E, T, E, S, T}
using mergesort.
Use a tree structure to display each call of sort and merge and the
corresponding part of the array a. Also add the arguments of
sort and merge on each edge of the tree.
Exercise 2: Multiway mergesort (30 points)
Develop a mergesort implementation based on the idea of doing k-way merges
instead of 2-way merges.
Analyze your algorithm, formulate a hypothesis regarding the best value of k,
and run experiments to validate your hypothesis.