> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/sorting-algorithms/homework.md).

# 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:

```java
Integer[][] input = {{0,  1,  2,  3},
                     {7,  6,  5,  4},
                     {0,  3,  1,  2},
                     {4,  7,  6,  5},
                     {9,  8, 11, 10}};
```

Here is the expected output given the sample input:

```java
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11]
```

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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/divide_conquer/IntroSort.java). The implementation of this strategy is provided to establish the baseline: [`HybridSortBaseline`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/hybrid/HybridSortBaseline.java). Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

## Tasks

* Create a class [`HybridSortHW`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/hybrid/HybridSortHW.java) inheriting [`HybridSort`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/hybrid/HybridSort.java)under the package [`hybridsort`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/sort/hybrid/).
* Override the `sort()` method and evaluate your program for robustness and runtime speeds using [`HybridSortTest`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/sort/HybridSortTest.java):
  * 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.

## Submission

* Commit and push everything under the [hybrid](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/sort/hybrid) 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.
  * 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](https://speakerdeck.com/jdchoi77/cs253-tries-2019).

## Results

Baseline: 20697

* Cannot run: 7
* Extremely slow: 6
* Code not found: 1

<table><thead><tr><th width="160" data-type="number"></th><th width="154" data-type="number"></th><th width="151" data-type="number"></th><th data-type="number"></th></tr></thead><tbody><tr><td>6873</td><td>21512</td><td>23027</td><td>25573</td></tr><tr><td>15545</td><td>21599</td><td>23209</td><td>25825</td></tr><tr><td>18443</td><td>21802</td><td>23411</td><td>25928</td></tr><tr><td>18618</td><td>22037</td><td>23417</td><td>28756</td></tr><tr><td>18676</td><td>22038</td><td>23622</td><td>29390</td></tr><tr><td>18933</td><td>22073</td><td>24988</td><td>43903</td></tr><tr><td>19787</td><td>22217</td><td>25289</td><td>67900</td></tr><tr><td>19851</td><td>22222</td><td>25531</td><td>99835</td></tr><tr><td>20378</td><td>22480</td><td>25536</td><td>217868</td></tr></tbody></table>