def quicksort(inputArray):
    """input: array
    output: new sorted array
    features: stable
    efficiency O(n^2) (worst case), O(n log(n)) (avg case), O(n) (best case):
    space complexity: O(n)
    method:
    Pick the last element in the array as the pivot.
    Separate values into arrays based on whether they are
    greater than, less than, or equal to the pivot.
    Recursively sort the greater than and less than arrays.
    Return an new array merging the sorted arrays and the pivot.
    """
    if len(inputArray) <= 1:
        return inputArray
    pivot = inputArray[-1]
    lesser = []
    greater = []
    equal = []
    for value in inputArray[:-1]:
        if value > pivot:
            greater.append(value)
        elif value < pivot:
            lesser.append(value)
        elif value == pivot:
            equal.append(value)
    lesser = quicksort(lesser)
    greater = quicksort(greater)
    return lesser + equal + [pivot] + greater