الگوریتم merge sort

[*sepid*]

سلام ... لطفا یکی به این سوال من جواب بده ...
آیا الگوریتم merge sort از فضایی بیشتر از آنچه که مورد نیاز ورودی است استفاده میکند یا خیر ؟
لطفا اگه میشه توضیح بدین ......

[xxxxx_xxxxx]

سلام
بله. اين الگوريتم به خاطر اين كه عمل مرتب سازي رو به صورت OutPlace انجام ميده، فضايي معادل فضاي ورودي احتياج داره.
همونطور كه مي دونيد اين الگوريتم به طور بازگشتي عمل مي كنه و در هر بار اجراي خودش، مجموعه اعداد رو به دو دسته تقسيم مي كنه و ضمن اين كار كوچكترين عدد رو كه دو اشاره گر بهش اشاره مي كنه رو به آرايه دوم منتقل مي كنند.
چون به آرايه ورودي احتياج داريم و نبايد طي عمل مرتب سازي تغييري كنه از يه آرايه ديگه استفاده مي كنيم. و در آخر محتويات آرايه دوم رو به آرايه اول منتقل مي كنيم.

[pesar irooni]

البته روش خاصی هم وجود داره که میشه بصورت درجا عمل merge رو انجام داد که مفصل تو کتاب هورویتز اومده. یعنی به جای استفاده از یک آرایه جداگانه از چندتا اشاره گر استفاده کرده و در همون زمان اون دو آرایه رو merge میکنه.