The sorting problem is well$-$studied in the computer science domain. There are many sorting algorithms available in academia to be used to sort data sets. Each sorting algorithm is a package of advantages, disadvantages, and limitations$.$ In this course, we have taken so far four sorting algorithms of $2$ different classes: Selection Sort, Insertion Sort, MergeSort, and QuickSort. This project asks you to implement these sorting algorithms and test their runtime against different input sizes.

Input Format

No input is required from the user.

Project requirements:

Introduction to the sorting problem.

Introduce all the sorting algorithms you have taken in this class, explain the algorithms, and write the algorithms and the Big$-$O for each algorithm.

Develop a Java program that includes the four sorting algorithms $($as methods$).$ Calculate the real run$-$time for each method and display it$.$

Graph the run time for all four algorithms against different input sizes.

Deliverables:

Write a report on your project that has the following information:

Your name, ID$,$ section, and course name. $($yes$,$ the course name! your professor teaches many sections and courses$)$

Write an introduction about the sorting problem.

Write a brief of each sorting algorithm and the pseudocode algorithm, and analyze the running time of each sorting algorithm using the Big O$.$ Remember when the best, average, and worst$-$case scenarios happen.

Your Java program should do the following:

a$.$ Create an array of integers of size $10$ and fill it with random integers.

b$.$ Make four copies of this array.

c$.$ Write four methods for sorting:

i$.$ Public int$[]$ SelectionSort$($int$[]$ ArrayCopy$1)$

ii$.$ Public int$[]$ InsertionSort$($int$[]$ ArrayCopy$2)$

iii. Public int$[]$ MergeSort$($int$[]$ ArrayCopy$3)$

iv$.$ Public int$[]$ QuickSort$($int$[]$ ArrayCopy$4)$

for each sorting method, print the real run time needed to sort the array.

d$.$ Redo steps a$,$ b and $c$ and increase the array size by appending one zero:

Keep increasing the array size until the run takes over $12$ hours.