می تونی از مرج کردن 2 به دوی اون ها استفاده کنی که با یه (O(n در مجموع همرو 2 به دو مرج کنی و تعداد آرایه هات نصف می شن. حالا مسئلرو ادامه بدی تا به یه آرایه برسی. می تونی بر اساس عناصر اولشون سورت کنی. حالا این عناصر رو تو مین هیپ یا ست بریزی. هر دفعه مینیمم رو خارج کنی و عضو بعدی مینیمم رو تو همون آرایه به دیتااستراکچرت(!) اضافه کن

اول، از هر آرایه اولیش رو میریزی تو یه heap minimum اسم اون heap رو میذارم S

یه آرایه تهی از n تا عدد هم می سازی به اسم A و اول خالی میذاریش.

حالا هر بار عدد بالای S رو می گیری و میذاری تو اولین خونه خالی A بعد اگر اون عدد از آرایه k-ام بود عدد بعدی آرایه kام رو به S اضافه می کنی(عدد اولی رو که در راس هرم بود پاک کردی). و همین طوری تا آخر.

این میشه $O(n\lg k)$ چون هر بار استفاده از heap از $O(\lg k)$ میشه و در کل برای هر n تا عدد 2 بار از heap استفاده می کنیم. :دی

پ.ن.: فکر نمی کردم بعد از این همه وقت کنکور خوندن بتونم سوال المپیاد حل کنم.

خوش باشی :دی

کوچیکترین عدد هر آرایه رو میریزیم تو ست(set) به همراه یه عدد که نشون دهنده ی آرایه ایه که این عدد توش بوده!
بعدش کوچیکترین عدد رو پیدا میکنیم با اردر لاگ k(اسشمو میزاریم x)
xرو از تو ست حذف میکنیم و عدد بعدیه آرایه ای که x توش بوده(در صورت وجود) رو به ست اضافه میکنیم و x رو به آرایه ی جواب اضافه میکنیم.
تو هر مرحله همینکارو تکرار میکنیم تا ست خالی بشه.
حالا آرایه ی جواب به صورت مرتب شده درست شده است.