آنچه در پاورپوینت Merge Sort خواهید دید

Overview

– ارائه دو الگوريتم براي ادغام دو ليست مرتب

– الگوريتم غير بازگشتي Merge Sort

– الگوريتم بازگشتي Merge Sort

Merge Sort

يكي از روش هاي مرتب سازي داخلي است.

در مرتب سازي به روش ادغام آرايه يا ليست مورد نظر طي چند مرحله به تعدادي آرايه يا ليست تك عضوي شكسته مي شود.

نكات:تعداد آرايه ها يا ليست هاي تك عضوي همان تعداد اوليه ي نودها يا اعضاي آرايه هستند .                  

طول ليست يا آرايه ي اوليه را N در نظر بگيريد.

به جاي آرايه ليست به كار مي بريم .

مرتب سازي ادغام به صورت تكرار ( غير بازگشتي )

دراين نسخه ورودي n ليست به طول 1است.اين ليست ها دوبه دوبا هم ادغام مي شوند تا n/2 ليست كه طول هر يك از آن ها 1 است به دست آيد (اگر n فرد باشد آنگاه يك ليست به طول 1 داريم). اين n/2 ليست دوبه دو با هم ادغام مي شوند و اين فرايند تا آنجا ادامه مي يابد كه در انتها به يك ليست برسيم.

در اسلايد بعدي اين فرايند نشان داده شده است.

تجزیه و تحلیل تابع MergeSort

تابعMergeSort  در چند مرحله از رکوردهای مرتب شونده عبور می کند.در مرحله ی اول لیست هایی به طول 1 ادغام می شوند.مرحله ی دوم طول لیست های ادغام شونده 2 است .درمرحله ی i ام لیست های ادغام شونده طول 2i-1 دارند.

در نتیجه تعداد کل مراحل عبور از داده ها log2n ]   [  است.

هر مرحله از مرتب سازی ادغام در زمان O(n) انجام می شود و زمان اجرای کل O(n logn) است.