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