3.6. Homework

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 . The implementation of this strategy is provided to establish the baseline: . Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

Tasks

• Create a class inheriting under the package .

• Override the sort() method and evaluate your program for robustness and runtime speeds using :

Submission

• Commit and push everything under the package.

• Submit hw1.pdf to Canvas.

Notes

• 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.

Results

Baseline: 20697

• Cannot run: 7

• Extremely slow: 6

• Code not found: 1