Quick Sort
$\textbf{Pseudocode for quicksort}$
$\text{QUICKSORT(A,p,r)}$
$\quad \textbf{if } p < r$
$\quad\quad \textbf{then} q \leftarrow \text{PARTITION}(A,p,r)$
$\quad\quad\quad \text{QUICKSORT}(A,p,q-1)$
$\quad\quad\quad\text{QUICKSORT}(A,q+1,r)$
${\color{Red}{\text{Initial call: }} }\text{QUICKSORT}(A,1,n)$
- ${\color{Red} {25}}\ 7\ 34\ 2\ 70\ 9\ 61\ 16\ 49\ 19$
- ${\color{Red} {25}}\ 7\ \color{blue}{2\ 34}\ 70\ 9\ 61\ 16\ 49\ 19$
- ${\color{Red} {25}}\ 7\ 2\ \color{blue}{9}\ 70\; \color{blue}{34}\; 61\ 16\ 49\ 19$
- ${\color{Red} {25}}\ 7\ 2\ 9 \ \color{blue}{16}\ 34\ 61\ \color{blue}{70}\ 49\ 19$
- ${\color{Red} {25}}\ 7\ 2\ 9\ 16\ \color{blue}{19} \; 61\ 70\ 49 \ \color{blue}{34}$
- $[7\ 2\ 9\ 16$ $19]$ ${\color{Red} {25}}\ [61\ 70\ 49$ $34]$
- $[{\color{Red} {7}}\ 2\ 9\ 16\ 19]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- $[[2]\ {\color{Red} {7}}\ [9\ 16\ 19]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- $[{\color{Red} {2\ 7}}\ [{\color{Red} {9}}\ [16\ 19]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- $[{\color{Red} {2\ 7}}\ [{\color{Red} {9}}\ [{\color{Red} {16}} \ 19]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- $[{\color{Red} {2}}\ {\color{Red} {7}}\ [{\color{Red} {9}}\ [{\color{Red} {16}} \ {\color{Red} {19}}]]]\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- ${\color{Red} {[2}}\ {\color{Red} {7[}}\ {\color{Red} {9}}\ {\color{Red} {16}} \ {\color{Red} {19]]}}\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- ${\color{Red} {[2}}\ {\color{Red} {7}}\ {\color{Red} {9}}\ {\color{Red} {16}} \ {\color{Red} {19]}}\ {\color{Red} {25}}\ [61\ 70\ 49\ 34]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[{\color{Red} {61}}\ \color{blue}{49\ 70}\ 34]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[{\color{Red} {61}}\ 49\; \color{blue}{34\ 70}]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }} [[49\ 34]\ {\color{Red} {61}}\ [70] ]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[[ {\color{Red} {49}}\ 34]\ {\color{Red} {61}}\ [70] ]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[[ [34]\ {\color{Red} {49}}]\ {\color{Red} {61}}\ [70] ]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[ {\color{Red} {[ [34]\ 49]}}\ {\color{Red} {61}}\ [70] ]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }}[ {\color{Red} {[34\ 49]}}\ {\color{Red} {61}}\ [70] ]$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }} [{\color{Red} {34\ 49}}\ {\color{Red} {61\ [70 ]}}] $
- ${\color{Red} {[2\ 7\ 9\ 16\ 19]\ 25\ }} {\color{Red} {[34\ 49}}\ {\color{Red} {61\ 70 ]}}\ $
- ${\color{Red} {[2\ 7\ 9\ 16\ 19\ 25\ }} {\color{Red} {34\ 49}}\ {\color{Red} {61\ 70] }}\ $
2-way MergeSort [Iterative version]
- $[25\ 7]\ [34\ 2]\ [70\ 9]\ [61\ 16]\ [49\ 19]$
- $[{\color{Red} {[7\ 25]}}\ {\color{Red} {[2\ 34]}}]\ [{\color{Red} {[9\ 70]}}\ {\color{Red} {[16\ 61]}}]\ [{\color{Red} {[19\ 49]}}]$
- $[{\color{Green} {[2\ 7\ 25\ 34 ]}}\ {\color{Green} {[9\ 16\ 61\ 70]}}]\ {\color{Green} {[19\ 49]}}$
- $[{\color{Blue} {[2\ 7\ 9\ 16\ 25\ 34\ 61\ 70]}}\ {\color{Green} {[19\ 49]}}]$
- $[{\color{Blue} {[2\ 7\ 9\ 16\ 19\ 25\ 34\ 49\ 61\ 70]}}$
$\textbf{MergeSort [Recursive version]}$
$\textbf{MERGE - SORT A[1...n]}$
- $\text{If } n = 1,$ done.
- Recursively sort $A[1...\left \lceil n/2 \right \rceil]$ and $A[\left \lceil n/2 \right \rceil + 1 ... n]. $
- ${\color{Red}{\text{“Merge"}}}$ the $2$ sorted lists.
$\qquad{\color{Red}{\text{Key subroutine: }}} \textbf{MERGE}$
- $[25\ 7\ 34\ 2\ 70]\ [9\ 61\ 16\ 49\ 19]$
- $[[25\ 7\ 34]\ 2\ 70]\ [9\ 61\ 16\ 49\ 19]$
- $[[{\color{Red} {[7\ 25]}}\ [34]]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
- $[[{\color{Red} {[7\ 25]}}\ {\color{Red} {[34]}}]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
- $[[{\color{Red} {[7\ 25\ 34]}}]\ [2\ 70]]\ [9\ 61\ 16\ 49\ 19]$
- $[{\color{Red} {[7\ 25\ 34]}}\ {\color{Red} {[2\ 70]}}]\ [9\ 61\ 16\ 49\ 19]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [9\ 61\ 16\ 49\ 19]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[9\ 61\ 16]\ [49\ 19]]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[[9\ 61]\ [16]]\ [49\ 19]]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[{\color{Red} {[9\ 61]}}\ [16]]\ [49\ 19]]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [[{\color{Red} {[9\ 61]\ [16]}}\ ]\ [49\ 19]]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [{\color{Red} {[9\ 16\ 61]}}\ [49\ 19]]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ [{\color{Red} {[9\ 16\ 61]}}\ {\color{Red} {[19\ 49]}}]$
- ${\color{Red} {[2\ 7\ 25\ 34\ 70]}}\ {\color{Red} {[9\ 16\ 19\ 49\ 61]}}$
- ${\color{Red} {[2\ 7\ 9\ 16\ 19\ 25\ 34\ 49\ 61\ 70]}}$