מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/מיזוג k-ארי/שאלה

במיון מיזוג ראינו את הפונקציה Merge, המקבלת שני מערכים ממוינים ומחזירה מערך ממוין של איחוד איבריהם בסיבוכיות לינארית. בשאלה זו נרחיב זאת למיזוג $\displaystyle k$ מערכים ממוינים.

נניח שברשותנו מערך Values-Arrays = [Values_1, ..., Values_k] (שים לב שזהו מערך של מערכים). אנא כתוב פונקציה יעילה K-Merge(Values-Array) המקבלת את מערך $\displaystyle k$ המערכים הממוינים, ומחזירה מערך ממוין של איחוד איבריהם.

לכל $\displaystyle 1\leq i\leq k$, נגדיר $\displaystyle n_{i}=$ Length(Values_i), ונניח ש$\displaystyle n_{i}\gg k$‏. אנא נתח תשובתך במונחי $\displaystyle n_{1},...,n_{k}$ ו$\displaystyle k$