Objective:

Evaluate and compare the Insertion Sort, Merge Sort, Heap Sort, and Quick Sort

algorithms on performance and efficiency. First program each of these in your

programming language of choice $($python$($preferred$)$ or $c++)$

Tasks:

Time Complexity Overview

Summarize the time complexity $($best$,$ average, worst$-$case$)$ for each

algorithm.

Highlight the main factor affecting each algorithm's time complexity.

Space Complexity Comparison

Briefly describe the space complexity for each sorting method.

Note which algorithms are in$-$place and which require extra space.

Stability and Adaptability Discussion

Identify which algorithms are stable.

Discuss how adaptable each algorithm is to nearly sorted data.

Empirical Performance Test

Test each algorithm with small arrays $($e$.$g$.,100$ elements$)$ and larger arrays

$($e$.$g$.,10,000$ elements$)$ of random and nearly sorted data.

Measure and compare the execution times.

Analysis and Conclusions

Based on your tests, discuss which algorithm performs best in different

scenarios $($small vs$.$ large datasets, random vs$.$ nearly sorted data$).$

Offer insights into the practical applications of each algorithm, considering

their time and space efficiency.

Deliverables:

A concise report that includes:

Source code

A summary table of time and space complexities.

A brief discussion on stability and adaptability.

A comparative chart of execution times from your empirical tests.

Final thoughts on the practical implications of your findings.

Evaluation Criteria:

Source code

Accuracy of the time and space complexity analysis.

Completeness of empirical testing and data collection.

Clarity and insightfulness of the final analysis and conclusions.