> [!NOTE] Defintion ('Deterministic' Quicksort) > Uses [[Divide & Conquer Algorithm|divide & conquer]]. Chose rightmost element as pivot at place it in its right position. Quicksort left and right partitions. Pseudocode below: ```pseudo ``` ```run-python # input: An array A[1,2,...,n] # output: Sort array A[1,2,...n] in ascending order n = len(A) pivot = A[n] S_smaller = []; S_larger = [] for i in range(n): if A[i] <= pivot: S_smaller.append(A[i]) else: S_larger.append(A[i]) ``` **function** _quicksort_(array) less, equal, greater **:=** three empty arrays **if** length(array) > 1 pivot **:=** _select any element of_ array **for each** x **in** array **if** x < pivot **then add** x **to** less **if** x = pivot **then add** x **to** equal **if** x > pivot **then add** x **to** greater quicksort(less) quicksort(greater) array **:=** concatenate(less, equal, greater) # Properties Worst-case asymptotic running time: $\Theta(n^{2})$ so worse than [[Merge Sort]].