История изменений

малость пооффтоплю:
недавно столкнулся с такой проблемой - нужно считать перцентили (или хотябы медиану) по массиву данных, разбитому на произвольные куски. склеить все вместе невыйдет - данных дофига. для большинства кусков медиана уже посчитана заранее. думал это довольно банальная задача - но готового решения или хотябы внятной методологии не нашел.
мой лучший вариант расчета медианы дает погрешность в 1.6% по верхнему квартилю (0.75) и 8.5% максимальную. алгоритм предельно топорный - медианы всех частей принимаем за новый массив, считаем по нему медиану и среднее и берем среднее от этих двух значений. тест проводился по 10кк наборам данных длинной от 10 до 10к элементов случайных целых чисел от 0 до 1000.
может есть у кого идеи как улучшить?

малость пооффтоплю:
недавно столкнулся с такой проблемой - нужно считать перцентили (или хотябы медиану) по массиву данных, разбитому на произвольные куски. склеить все вместе невыйдет - данных дофига. для большинства кусков медиана уже посчитана заранее. думал это довольно банальная задача - но готового решения или хотябы внятной методологии не нашел.
мой лучший вариант дает погрешность в 1.6% по верхнему квартилю (0.75) и 8.5% максимальную. алгоритм предельно топорный - медианы всех частей принимаем за новый массив, считаем по нему медиану и среднее и берем среднее от этих двух значений. тест проводился по 10кк наборам данных длинной от 10 до 10к элементов случайных целых чисел от 0 до 1000.
может есть у кого идеи как улучшить?