external merge

نقل قول:

لطفا الگوریتم external mergesort رو شرح بدین

وقتی داده های یه فایل خیلی بزرگ که تو حافظه جا نمیشه رو میخوای sort کنی، تیکه تیکه لود میکنی و sort میکنی و به قسمتهای کوچکتر سورت شده تبدیلش میکنی. بعد فایل ها رو با هم merge میکنی. برای merge کردن n تا فایل هم، هرچقدر که فایلهات بزرگ باشه، از نظر حافظه محدودیت خاصی نداری ولی معمولا میگن از 20-30 تیکه بیشتر نشه، بهتره.

نقل قول:

الگوریتمشو طوری توضیح بدین که برای مقایسه ها از آرایه استفاده نکنیم.

اون دیگه میشه یه روش دیگه که شدیدا هم کند میشه اگر نخوای اینجور که گفتم کار کنی. تو باید تکه های کوچکتر بخونی و تو آرایه بریزی.
مثلا اگر فرضا یه فایل 5 Gigabyte داری و فقط 256 Megabyte حافظه داری، میتونی فایل رو در 20 تیکه 256 MB بخونی و 20 تا فایل سورت شده جزئی از اطلاعات درست کنی و بعد اونها رو merge کنی.