سوال:
چرا هیچ الگوریتم مرتب سازی بر اساس مقایسه کمتر nlgn نیست .من متوجه نمیشم اثباتش رو که با درخت تصمیم ثابت میشه .ممکنه کاملا تشریح کنین.
یه روش راحت برای حل این مسله بصورت سر انگشتی اینه:
عناصر مرتب شده یعنی اینکه عناصر بترتیب سر جاشون هستن . به تعبیری شما باید بدونید که هر عنصری از عناصر قبلی اش بزرگتر و از عناصر قبلیش کوچکتره از اونجایی که تعداد عناصر n هستش پس شما n تا پیمایش داری برای هر عنصر , و برای اینکه بدونی هر عنصر در سر جای درستش هست میشه از یک الگوریتم مثله جستجوی دودیی که از مرتبه log n هستش استفاده کرد که در کمترین حالت همون nlgn میشه . ولی در حالت کلی به این اثبات نمی گین ولی کمک می کنه بفهمی چرا کمتر از nlgn نمیشه .
اینم اثباتش :