external merge

[akhondak]

سلام
لطفا الگوریتم external mergesort رو شرح بدین.اگر نخواهیم اعدادی که از فایل میخونیم رو در آرایه بریزیم چون ممکنه 12000 عدد باشه باید چکار کرد؟
یعنی الگوریتمشو طوری توضیح بدین که برای مقایسه ها از آرایه استفاده نکنیم.

[someCoder]

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

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

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

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