This assignment is intended to make you implement several different sorting algorithms, and the means to analyze their
performance. This assignment is in two parts: a program, and an analysis.
You’ve been given a scattered list of small monsters present in the Knightrola region. You need to evaluate six means of
comparison-based sort to get these monsters in order.
You need to implement six sorts for the monster structure:
• Bubble sort
• Selection sort
• Insertion sort
• Quick sort
• Merge sort
• Merge sort, switching to insertion sort at ? ≤ 25
Data Structures and Prototypes We’ve given you two template C files that will help you with implementation.
• integer-sorts-template.c: Contains implementation code for bubble, selection, and quick sorts against integer arrays. IMPLEMENT MERGE SORT AND INSERTION SORT HERE FIRST, AND GET THEM WORKING, TO DEVELOP YOUR UNDERSTANDING OF THE ALGORITHMS.
• monster-sorts-template.c: Contains the shell for sorting monsters via all six sorts. You may use your code from
integer-sorts-template.c directly, modifying it as necessary to work on the more complex data structures. Don’t
change the structures, the function headers, or any of the helper functions.