Sorting Algorithms Benchmark (Merge Sort, Insertion Sort, Timsort)

This project compares the performance of three sorting algorithms: • Merge Sort (O(n log n)) • Insertion Sort (O(n²)) • Timsort — Python’s built-in sorting algorithm used in sorted() and list.sort()

The benchmark was executed on datasets of different sizes using the timeit module.

Results Summary • Insertion Sort becomes extremely slow as input size grows. Its quadratic complexity makes it impractical for large data. • Merge Sort performs well with predictable O(n log n) behavior. It is significantly faster than Insertion Sort. • Timsort consistently shows the best performance. It is a hybrid algorithm combining merge sort and insertion sort. Its strength lies in being adaptive, meaning it exploits already sorted segments of data.

Conclusion

The empirical results confirm the theoretical expectations: • Merge Sort is efficient. • Insertion Sort is only useful for small inputs. • Timsort is significantly faster than both, which explains why Python developers rely on built-in sorting functions rather than implementing sorting algorithms manually.