def quick_sort(arr):
    # make 2 groups
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # pick random number as pivot
    ref = random.choice(arr)

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    
    left = quick_sort(left)
    right = quick_sort(right)
    
    return left + [ref] * ref_count + right