This section explains the homework assignment regarding Hybrid Sort.
Your task is to write a program that sorts a 2D-array of comparable keys into an 1D-array where all the keys are sorted in ascending order. Here is a sample input to your program:
Here is the expected output given the sample input:
Each row in the input array has one of the following properties:
Sorted in ascending order (e.g., the 1st row).
Sorted in descending order (e.g., the 2nd row).
Mostly sorted in ascending order (e.g., the 3rd row).
Mostly sorted in descending order (e.g., the 4th row).
Randomly distributed (e.g., the 5th row).
The easiest way is to merge all rows in the input array into an 1D-array then sort it using IntroSort. The implementation of this strategy is provided to establish the baseline: HybridSortBaseline. Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.
Create a class HybridSortHW inheriting HybridSortunder the package hybridsort.
Override the sort() method and evaluate your program for robustness and runtime speeds using HybridSortTest:
Try different input arrays; you are responsible for the robustness of your program.
Try different configurations for speed comparison (e.g., row size, column size, shuffle ratio).
Write the report hw1.pdf describing the logic behind your mechanism and the speed comparison against the baseline.
Commit and push everything under the hybrid package.
Submit hw1.pdf to Canvas.
You are not allowed to:
Use any implementation that is not written by you nor provided by this course.
Call any sorting methods built-in Java or 3rd-party libraries.
Merge all rows first and apply a fancy sorting algorithm to the 1D array as the baseline does.
The input matrix can:
Contain an arbitrary number of rows, where the size of each row is also arbitrary.
Include any type of the keys that are Comparable.
Baseline: 20697
Cannot run: 7
Extremely slow: 6
Code not found: 1