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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/sorting-algorithms/homework.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.