# Quicksort Pseudocode

Now that we’ve seen an example of how quicksort works, let’s walk through the pseudocode of a quicksort function. The function itself is very simple, as shown below.

``````1function QUICKSORT(ARRAY, START, END)
2    # base case size <= 1
3    if START >= END then
4        return
5    end if
6    PIVOTINDEX = PARTITION(ARRAY, START, END)
7    QUICKSORT(ARRAY, START, PIVOTINDEX – 1)
8    QUICKSORT(ARRAY, PIVOTINDEX + 1, END)
9end function``````

This implementation of quicksort uses a simple base case on lines 3 through 5 to check if the array is either empty, or contains one element. It does so by checking if the `START` index is greater than or equal to the `END` index. If so, it can assume the array is sorted and just return it without any additional changes.

The recursive case is shown on lines 6 - 8. It simply uses a helper function called `partition` on line 6 to partition the array based on a pivot value. That function returns the location of the pivot value, which is stored in `pivotIndex`. Then, on lines 7 and 8, the quicksort function is called recursively on the two partitions of the array, before and after the `pivotIndex`. That’s really all there is to it!

Let’s look at one way we could implement the `partition` function, shown below in pseudocode.

`````` 1function PARTITION(ARRAY, START, END)
2    PIVOTVALUE = ARRAY[END]
3    PIVOTINDEX = START
4    loop INDEX from START to END
5        if ARRAY[INDEX] <= PIVOTVALUE
6            TEMP = ARRAY[INDEX]
7            ARRAY[INDEX] = ARRAY[PIVOTINDEX]
8            ARRAY[PIVOTINDEX] = TEMP
9            PIVOTINDEX = PIVOTINDEX + 1
10        end if
11    end loop
12    return PIVOTINDEX – 1``````

This function begins on lines 2 and 3 by setting initial values for the `pivotValue` by choosing the last element in the array, and then setting the `pivotIndex` to 0. Then, the loop on lines 4 through 11 will look at each element in the array, determine if it is less than or equal to `pivotValue`, and swap that element with the element at `pivotIndex` if so, incrementing `pivotIndex` after each swap.

At the end, the value that was originally at the end of the array will be at location `pivotIndex – 1`, so we will return that value back to the `quicksort` function so it can split the array into two parts based on that value.