InternshipSearching and sorting
Binary search and merge sort, written out.
Binary search
On sorted data, check the middle and throw away half. Doubling the data adds only one more step.
Expected output
3 -1
Merge sort
Split the list in half, sort each half, then merge. It is O(n log n) even in the worst case.
Expected output
[1, 2, 5, 9]