اگر رویه ی فراخوانی مرتب سازی سریع به صورت بازگشتی این چنین باشد
if (Low>High)
return
else
}
partition (A,Low,pivot point)
Quick Sort (A,Low,pivotpoint-1)
Partition(A,Pivot Point+1,high)
{


می دانیم در حالت کلی مرتب سازی سریع از آرایه ی اصلی برای مرتب سازی عناصر استفاده می کند، اما چون یک الگوریتم بازگشتی است و در هر فراخوانی باید دو اندیس در پشته ذخیره شوند، بنابراین در بدترین حالت همواره یکی از زیر لیست های ایجاد شده ( در صورت داشتن آرایه ای صعودی یا نزولی ) تهی است، و دیگری n-1 عنصر خواهد داشت که در این صورت الگوریتم باید n-1 بار به صورت بازگشتی فراخوانی کند، بنابراین عمق پشته بازگشتی از مرتبه n خواهد بود و الگوریتم به فضای کمکی [tex]\theta(n)[/tex] نیاز خواهد داشت

برای بهبود بخشیدن به این فضای مصرفی می توان در هر مرحله زیر لیست کوچکتر را زودتر فراخوانی کرد. در این حالت عمق پشته کمترین شد را خوهد داشت و بیشترین عمق زمانی رخ می دهد که در هر بار لیست ورودی به دو نیمه تقسیم شود که در این حالت عمق پشته و در نتیجه فضای اضاغی مور نیاز [tex]\theta(nlogn)[/tex] خواهد بود
اگر در هر فراخوانی الگوریتم مرتب سازی سریع زیر لیست کوچکتر زودتر به الگروریتم داده شود آنگاه در حالتی که همواره یکی از لیست ها تهی است و دیگری شامل n-1 عنصر عمثق پشته از مرتبه [tex]\theta(1)[/tex] می باشد


می شه این پشته را کمی بیشتر توضیح بدین یا حالا با یک مثالی که با فراخوانی لیست بزرگتر می شود [tex]\theta(n)[/tex] و با فراخوانی لیست کوچکتر می شود [tex]\theta(1)[/tex]

خیلی ممنون