Numbers are generated randomly and stored in an array. Write a program to find the median value of the array as soon as new numbers are generated. Imp

Numbers are generated randomly and stored in an array. Write a program to find the median value of the array as soon as new numbers are generated. Improve your solution.

We can optimise this by first using quick sort. The question states you must determine the median as new numbers are generated. Once sorted, you could add that doing a binary search O(log n), insert O(n) and returning the middle index 0(1) would make subsequent calculations 0(n), hence better than O(nlogn) if its done all the time.
Insertion sort (n^2)
Dynamic statistic, refer to clrs

Difference between merge and quick, when to use which?

Difference between merge and quick, when to use which?

Merge sort is stable, always O(nlog(n)), but need external storage O(n)
Quick sort is in place sorting with O(nlogn), but the worst case performance for quick sort is O(n^2)
Merge sort and heap sort is stable, others are not stable