March - this is not a complete answer, but instead addresses the gathering of indices since that seems to be important. Here's a comparison of some methods, tested only on my cigar-lounge netbook so caveat lector.

OP - Virgil's original (position based), Virgil - Virgil's adaptation of my first comment, CMT. 2/3 - my second and third comments (gathered tuples and pure sparse array), post - the code below inserted into Virgil's first snippet.

I stopped timing on the OP method at 200x200 array - it was nearing a minute on my poor netbook (and "post" was ~600X faster at that data point)...

Fill was ~0.5 for these tests. Times are for complete results from Virgil's code, just with index gathering changed.

"post" code:

cindices = Module[{sa = SparseArray[output], xx, yy, sa1, sa2},
  sa1 = sa["NonzeroValues"];
  xx = GatherBy[Range@Length@sa1, sa1[[#]] &];
  sa2 = sa["NonzeroPositions"];
  yy = sa2[[#]] & /@ xx;
  Transpose[{sa1[[xx[[All, 1]]]], yy}]];

Benchies:

![enter image description here][1]

I hope you find use in this. [1]: https://i.sstatic.net/csQJi.png

March - this is not a complete answer, but instead addresses the gathering of indices since that seems to be important. Here's a comparison of some methods, tested only on my cigar-lounge netbook so caveat lector.

OP - Virgil's original (position based), Virgil - Virgil's adaptation of my first comment, CMT. 2/3 - my second and third comments (gathered tuples and pure sparse array), post - the code below inserted into Virgil's first snippet.

I stopped timing on the OP method at 200x200 array - it was nearing a minute on my poor netbook (and "post" was ~600X faster at that data point)...

Fill was ~0.5 for these tests. Times are for complete results from Virgil's code, just with index gathering changed.

"post" code:

cindices = Module[{sa = SparseArray[output], xx, yy, sa1, sa2},
  sa1 = sa["NonzeroValues"];
  xx = GatherBy[Range@Length@sa1, sa1[[#]] &];
  sa2 = sa["NonzeroPositions"];
  yy = sa2[[#]] & /@ xx;
  Transpose[{sa1[[xx[[All, 1]]]], yy}]];

Benchies:

I hope you find use in this.

March - this is not a complete answer, but instead addresses the gathering of indices since that seems to be important. Here's a comparison of some methods, tested only on my cigar-lounge netbook so caveat lector.

OP - your original, Virgil - Virgil's adaptation of my first comment, CMT. 2/3 - my second and third comments (gathered tuples and pure sparse array), post - the code below inserted into Virgil's first snippet.

I stopped timing on your OP method at 200x200 array - it was nearing a minute on my poor netbook (and "post" was ~600X faster at that data point)...

Fill was ~0.5 for these tests.

"post" code:

cindices = Module[{sa = SparseArray[output], xx, yy, sa1, sa2},
  sa1 = sa["NonzeroValues"];
  xx = GatherBy[Range@Length@sa1, sa1[[#]] &];
  sa2 = sa["NonzeroPositions"];
  yy = sa2[[#]] & /@ xx;
  Transpose[{sa1[[xx[[All, 1]]]], yy}]];

Benchies:

![enter image description here][1]

I hope you find use in this. [1]: https://i.sstatic.net/csQJi.png

March - this is not a complete answer, but instead addresses the gathering of indices since that seems to be important. Here's a comparison of some methods, tested only on my cigar-lounge netbook so caveat lector.

OP - Virgil's original (position based), Virgil - Virgil's adaptation of my first comment, CMT. 2/3 - my second and third comments (gathered tuples and pure sparse array), post - the code below inserted into Virgil's first snippet.

I stopped timing on the OP method at 200x200 array - it was nearing a minute on my poor netbook (and "post" was ~600X faster at that data point)...

Fill was ~0.5 for these tests. Times are for complete results from Virgil's code, just with index gathering changed.

"post" code:

cindices = Module[{sa = SparseArray[output], xx, yy, sa1, sa2},
  sa1 = sa["NonzeroValues"];
  xx = GatherBy[Range@Length@sa1, sa1[[#]] &];
  sa2 = sa["NonzeroPositions"];
  yy = sa2[[#]] & /@ xx;
  Transpose[{sa1[[xx[[All, 1]]]], yy}]];

Benchies:

![enter image description here][1]

I hope you find use in this. [1]: https://i.sstatic.net/csQJi.png