df = pd.DataFrame({'col1': randint(0, 100, 1000), 'col2': randint(0, 2, 1000)})
df.sort_values(['col1', 'col2'], inplace=True)
cnt = df.groupby(['col1', 'col2']).col1.count()
df['rk'] = np.hstack([list(range(n)) for n in cnt])
df.sort_values(['col1', 'rk'], inplace=True)
Sort but have uniform distribution for a second variable if values are same