Добрый вечер!
Можно воспользоваться тем, что после объединения 2-х массивов len(seg1) = n1 и len(seg2) = n2 с большой вероятностью получится массив с меньшей длиной чем n1+n2 , из-за пересечения отрезков. Объединять не сразу все массивы, а третий с результатом объединения первых двух.
И в сортировке слиянием следующий элемент можно искать не инкрементом, а поиском [забыл название]: просматриваются 1, 2, 4, 8... элементы; если искомый элемент находится между 2ⁱ и 2ⁱ⁺¹, то ищем бинарным поиском между ними. Это позволит в таких случаях: arr[{{1,100}},{{1,2},{2,3}, ..., {99,100}}] сливать массивы не за O(n), а за O(log n), при этом не сильно ухудшая время сливания массивов с равномерным распределением отрезков.
И первый и второй вариант зависит от реального распределения отрезков, так что надо тестить.