Function to generate nearly sorted numbers
def nearly_sorted_numbers(n):
    if n &gt;= 100:
        x = (int)(n/10)


Use int(n//10), the // explicitly request integer division and python doesn't have casts

    elif n &gt;= 10:
        x = 9
    else:
        x = 4 


I wouldn't name the variable x, as it gives no hint as to what it means. I'd also wonder whether it wouldn't be better as a parameter to this function. It seems out of place to be deciding that here.

    numbers = []    
    for i in range(1,n):
        if i%x==0: 
            numbers.append(random.randint(0,n))
        else:
            numbers.append(i)
return numbers