مرتب سازی ادغامی چندمرحله ای الگوریتمی است که با ادغام تکه ها به تکه هایی بزرگ تر باعث کاهش تعداد اجرا در هر تکرار از حلقۀ اصلی می شود و برای مرتب سازی خارجی استفاده می شود.
مرتب سازی ادغامی مجموعه ای از داده را به تکه هایی مرتب تجزیه می کند و سپس بارها و بارها تکه ها را ادغام می کند تا تنها یک تکه، مجموعه ای مرتب شده، باقی بماند.
مرتب سازی ادغامی عادی از چهار فایل استفاده می کند و آن ها را به صورت یک دسته فایل های ورودی و یک دسته فایل های خروجی سازمان دهی می کند. مجموعهٔ داده ها به طور مساوی بین دو فایل توزیع شده، یا به عنوان تکهٔ مرتب شده یا در ساده ترین حالت، یک داده مفرد که می توان آن را یک تکه مرتب شده با اندازه ۱ در نظر گرفت. هنگامی که همهٔ مجموعهٔ داده ها به دو فایل منتقل می شوند، این دو فایل به فایل های ورودی برای اولین ادغام تبدیل می شوند. در هر بار ادغام، دو فایل ورودی ادغام می شوند، خروجی ها به صورت متناوب بین دو فایل خروجی توزیع، و دوباره به طور مساوی بین دو فایل خروجی اجرا می شود ( تا آخرین مرحلهٔ ادغام ) . هنگامی که تمام تکه ها از دو فایل ورودی با هم ادغام شدند و خروجی حاصل شد، برای ادغام بعدی فایل های خروجی به فایل های ورودی تبدیل شده و بالعکس. در هر مرحله تعداد تکه ها به نصف کاهش می یابد، مانند ۶۴٬۳۲٬۱۶٬۸٬۴٬۲٬۱. در آخرین مرحلهٔ ادغام، هر کدام از دو فایل ورودی تنها یک تکه مرتب شده دارند ( نصف مجموعه ای از داده ها ) ، و نتیجهٔ ادغام، یک تکهٔ مرتب شده ( مجموعه دادهٔ طبقه بندی شده ) در یکی از فایل های خروجی است. این روش در مرتب سازی ادغامی با استفاده از درایوهای نواری نیز توصیف شده است.
اگر تنها سه فایل وجود داشت، مرتب سازی ادغامی دو فایل مرتب شده را در یک فایل ادغام کرده، سپس تکه را به طور مساوی بین دو فایل خروجی توزیع می کند. در نتیجه در هر تکرار تعداد تکه ها به نصف کاهش می یابد، توزیع مجدد تعداد تکه ها را کاهش نمی دهد ( اندازهٔ عامل یک است ) . تعداد کاهش تکه ها در هر تکرار را می توان به اندازه جذر۲ در نظر گرفت. اگر ۵ فایل وجود داشت، الگوی ادغام به تناوب بین ادغام ۳ راهه و ادغام ۲ راهه اجرا می شود که به طور متوسط عامل کاهش جذر ۶≈۲٫۴۵. به طور کلی، برای هر تعداد فایل زوج، هر مرحله از مرتب کردن بر اساس مرتب سازی ادغامی عادی تعداد تکه ها را به نصف کاهش می دهد، یا برای تعداد فرد فایل O، در هر تکرار از مرتب کردن بر اساس مرتب سازی ادغامی عادی تعداد تکه ها به جذر ( ( O2 - 1 ) /4 ) کاهش می باید.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمرتب سازی ادغامی مجموعه ای از داده را به تکه هایی مرتب تجزیه می کند و سپس بارها و بارها تکه ها را ادغام می کند تا تنها یک تکه، مجموعه ای مرتب شده، باقی بماند.
مرتب سازی ادغامی عادی از چهار فایل استفاده می کند و آن ها را به صورت یک دسته فایل های ورودی و یک دسته فایل های خروجی سازمان دهی می کند. مجموعهٔ داده ها به طور مساوی بین دو فایل توزیع شده، یا به عنوان تکهٔ مرتب شده یا در ساده ترین حالت، یک داده مفرد که می توان آن را یک تکه مرتب شده با اندازه ۱ در نظر گرفت. هنگامی که همهٔ مجموعهٔ داده ها به دو فایل منتقل می شوند، این دو فایل به فایل های ورودی برای اولین ادغام تبدیل می شوند. در هر بار ادغام، دو فایل ورودی ادغام می شوند، خروجی ها به صورت متناوب بین دو فایل خروجی توزیع، و دوباره به طور مساوی بین دو فایل خروجی اجرا می شود ( تا آخرین مرحلهٔ ادغام ) . هنگامی که تمام تکه ها از دو فایل ورودی با هم ادغام شدند و خروجی حاصل شد، برای ادغام بعدی فایل های خروجی به فایل های ورودی تبدیل شده و بالعکس. در هر مرحله تعداد تکه ها به نصف کاهش می یابد، مانند ۶۴٬۳۲٬۱۶٬۸٬۴٬۲٬۱. در آخرین مرحلهٔ ادغام، هر کدام از دو فایل ورودی تنها یک تکه مرتب شده دارند ( نصف مجموعه ای از داده ها ) ، و نتیجهٔ ادغام، یک تکهٔ مرتب شده ( مجموعه دادهٔ طبقه بندی شده ) در یکی از فایل های خروجی است. این روش در مرتب سازی ادغامی با استفاده از درایوهای نواری نیز توصیف شده است.
اگر تنها سه فایل وجود داشت، مرتب سازی ادغامی دو فایل مرتب شده را در یک فایل ادغام کرده، سپس تکه را به طور مساوی بین دو فایل خروجی توزیع می کند. در نتیجه در هر تکرار تعداد تکه ها به نصف کاهش می یابد، توزیع مجدد تعداد تکه ها را کاهش نمی دهد ( اندازهٔ عامل یک است ) . تعداد کاهش تکه ها در هر تکرار را می توان به اندازه جذر۲ در نظر گرفت. اگر ۵ فایل وجود داشت، الگوی ادغام به تناوب بین ادغام ۳ راهه و ادغام ۲ راهه اجرا می شود که به طور متوسط عامل کاهش جذر ۶≈۲٫۴۵. به طور کلی، برای هر تعداد فایل زوج، هر مرحله از مرتب کردن بر اساس مرتب سازی ادغامی عادی تعداد تکه ها را به نصف کاهش می دهد، یا برای تعداد فرد فایل O، در هر تکرار از مرتب کردن بر اساس مرتب سازی ادغامی عادی تعداد تکه ها به جذر ( ( O2 - 1 ) /4 ) کاهش می باید.
