Вы можете сжать списки и отсортировать результат. Сортировка кортежей должна по умолчанию сортироваться по первому элементу.
>>> xs = [3,2,1]
>>> ys = [1,2,3]
>>> points = zip(xs,ys)
>>> points
[(3, 1), (2, 2), (1, 3)]
>>> sorted(points)
[(1, 3), (2, 2), (3, 1)]
А затем снова распаковать их:
>>> sorted_points = sorted(points)
>>> new_xs = [point[0] for point in sorted_points]
>>> new_ys = [point[1] for point in sorted_points]
>>> new_xs
[1, 2, 3]
>>> new_ys
[3, 2, 1]