Қандай алгоритмикӣ мураккабият дар амалиёти пайваст кардани чанд массив бо сипас тартиб додани натиҷаи ба даст овардашуда вуҷуд дорад?

Бозори чанд масивро якҷоя кардан ва сипас натиҷаро ба тартиб даровардан одатан дорои мураккабии алгоритмӣ чунин аст:

1. Гуфта шавад, ки мо k масив дорем, ки ҳаҷми умумии онҳо n аст.
2. Якҷоя кардани масивҳо амалияи нусхагирии элементҳо мебошад, ки дар O(n) иҷро мешавад.
3. Тартиб додани масиви якҷоя дар вақти O(n log n) анҷом меёбад, агар алгоритми самараноки тартиб додан (масалан, тезтар ё тартиби бо ҳам пайваст) истифода шавад.

Ҳамагӣ, мураккабии умумӣ — O(n log n).

Агар масивҳои ибтидоӣ аллакай тартибдодашуда бошанд, метавон алгоритми пайвасткунии к масиви тартибдодашударо истифода бурд, ки натиҷаро дар O(n log k) ба даст меорад, ки дар мавриди шумораи зиёди масивҳо самараноктар аст.