Lab 3 - Binary Insertion Sort

1. Open your Homework 2 program in IntelliJ (or another IDE where it can be modified).
2. If the latest version of your work is not on Bitbucket (or GitHub), create a commit "Before lab" and push it. Do this before starting the lab. If necessary, review the materials from the first lab.
3. The teacher will assign you a partner.
4. In Moodle, open your last submission and show the submission time, the lecturer’s latest comment (must contain "ok"), and the measurement results graph.
   NB! All automated tests must pass and all sources must be referenced.
5. Explain your solution to your partner and compare the running times. Your partner will do the same.
6. Together with your partner, implement a third version of binary insertion sort that is different from both of your previous versions. Possible options include:
   • binary search implemented with a loop inside the sorting method
   • a separate recursive binary search method
   • a separate non-recursive binary search method
   • Arrays.binarySearch
   • ...
7. Test the new solution and compare its speed with your previous implementations.
8. On one computer, combine three methods:
   • your method
   • your partner’s method
   • the new method
   Create a new comparison table and graph (one per pair, only binary insertion sort versions). NB! All measurements must be done on the same computer. The graph must show all three methods.
9. Create a commit "Cooperation with Partner Name" and push it to Bitbucket (or GitHub). Your partner does the same.
10. Show the teacher:
    • the final commit
    • your program
    • the new comparison table and graph
11. The teacher will discuss the results and ask questions about the performance of the different variants.
12. The teacher assigns the grade. Then fill in the Homework 2 defense in Moodle.