Is it possible to calculate the median of the sample incrementally?

Question

Algorithms

Good afternoon.
There is a program that receives random numbers over the network and calculates statistics on them. The program must be able to run for a long time. The problem with calculating the median - according to the definition, you need to sort the selection and take the value in the middle of the array. That is, you need to store all the received values. But with large amounts of incoming data / long running time, the memory will run out and the program will crash. Is there a way out?

Answer 1

There is, and it's called Streaming Median:
https://programmingpraxis.com/2012/05/29/streaming...
https://habr.com/post/264987/
https://www.cse.wustl.edu/ ~jain/papers/ftp/psqr.pdf