Repository: pytorch
Issue: Make topk sort stable
Labels: triaged,enhancement,module: determinism,OSS contribution wanted,module: sorting and selection

## 🐛 Bug

torch.topk with sorted=True doesn't return a result that is consistent across different values of k when dealing with duplicates values. The position of duplicated values in the returned sorted indices varies with k. The behavior varies between CPU and CUDA, and it's inconsistent both between and within the two backends.

This affects the reference implementation for computing accuracy in e.g. imagenet classification ([link](https://github.com/pytorch/examples/blob/ee964a2eeb41e1712fe719b83645c79bcbd0ba1a/imagenet/main.py#L407)), in the sense that passing topk=(1,5) or topk=(1,10) might give different top1 accuracies. The effect is especially notable on highly quantized models, where it's more common to have duplicated values in the output of a layer.

## To Reproduce

On CPU:

```python
In [1]: import torch

In [2]: x = torch.Tensor([1, 2, 5, 4, 5])

In [3]: print(x.topk(1, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5.]),
indices=tensor([4]))

In [4]: print(x.topk(2, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5.]),
indices=tensor([2, 4]))

In [5]: print(x.topk(3, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4.]),
indices=tensor([2, 4, 3]))

In [6]: print(x.topk(4, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4., 2.]),
indices=tensor([2, 4, 3, 1]))

In [7]: print(x.topk(5, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4., 2., 1.]),
indices=tensor([2, 4, 3, 1, 0]))
```

On CUDA:

```python
In [1]: import torch

In [2]: y = torch.Tensor([1, 2, 5, 4, 5]).cuda()

In [3]: print(y.topk(1, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5.], device='cuda:0'),
indices=tensor([2], device='cuda:0'))

In [4]: print(y.topk(2, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5.], device='cuda:0'),
indices=tensor([4, 2], device='cuda:0'))

In [5]: print(y.topk(3, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4.], device='cuda:0'),
indices=tensor([4, 2, 3], device='cuda:0'))

In [6]: print(y.topk(4, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4., 2.], device='cuda:0'),
indices=tensor([2, 4, 3, 1], device='cuda:0'))

In [7]: print(y.topk(5, largest=True, sorted=True))
torch.return_types.topk(
values=tensor([5., 5., 4., 2., 1.], device='cuda:0'),
indices=tensor([2, 4, 3, 1, 0], device='cuda:0'))
```

## Expected behavior

The indices should be always in the same order independently of the value of k. Ideally they should also be in the same order between CPU and GPU. 

## Environment

Reproduced on latest pytorch-nightly.

```
python collect_env.py
Collecting environment information...
PyTorch version: 1.3.0.dev20190917
Is debug build: No
CUDA used to build PyTorch: 10.0.130

OS: Ubuntu 16.04.6 LTS
GCC version: (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609
CMake version: Could not collect

Python version: 3.6
Is CUDA available: Yes
CUDA runtime version: 10.0.130
GPU models and configuration:
GPU 0: Quadro P6000
GPU 1: Quadro P6000
GPU 2: Quadro P6000

Nvidia driver version: 418.67
cuDNN version: /usr/lib/x86_64-linux-gnu/libcudnn.so.7.5.0

Versions of relevant libraries:
[pip] numpy==1.17.2
[pip] torch==1.3.0.dev20190917
[pip] torchvision==0.5.0a0+e8b830f
[conda] blas                      1.0                         mkl
[conda] mkl                       2019.4                      243
[conda] mkl-service               2.3.0            py36he904b0f_0
[conda] mkl_fft                   1.0.14           py36ha843d7b_0
[conda] mkl_random                1.1.0            py36hd6b4f25_0
[conda] pytorch                   1.3.0.dev20190917 py3.6_cuda10.0.130_cudnn7.6.2_0    pytorch-nightly
[conda] torchvision               0.5.0.dev20190917      py36_cu100    pytorch-nightly
```


cc @ezyang @gchanan @zou3519 @jerryzh168 @jianyuh @dzhulgakov @raghuramank100 @jamesr66a