Здравствуйте, #John, Вы писали:

J>Имеется массив массивов отрезков, которые надо объеденить в один:
J>arr[seg1,seg2,seg3,....];
J>seg1=[{x11,x12},{x13,x14},{x15,x16},...], seg2=[{x21,x22},{x23,x24},{x25,x26},...],...
J>x1<x2<x3<.., 0<x<1,000,000,
...
J>Самый не оптимальный и быстрый вар. который напрашивается — это пройтись по каждой ноде в кажом seg[2..n] в arr и объединять их с нодами seg1, при каждом объединение проходя по каждой ноде из seg1, т.е. за время O(n).
J>Но, возномжно можно как-то быстрее искать ноды в seg1 с которыми надо объеденять ноды из seg[2..n]?

Я правильно понял, что внутри всех массивов отрезки упорядочены?
Тогда сортировка слиянием, точнее, её этап "Соединение двух упорядоченных массивов в один".