algorithm - How to shuffle rows with keeping two fields in original order? -

i have array of rows 4 fields:

group,name,key,value

i need "shuffle" array, resulting array should comply following rule: every key-value pair having same group should have same order in original array

here's 1 possible algorithm, requires auxiliary array of same size original array. it's o(n), makes several passes on original array.

1. using stable counting sort algorithm, make copy of original array sorted group. keep histogram use in step 3.

2. use fisher-yates shuffle algorithm shuffle original array in place.

3. make final pass on shuffled array created in step 2. each row, replace key , value entries next unused key , value entries sorted array created in step 1.

the counting sort algorithm assumes group values integers in small range, ideally smaller total number of rows in original array. if not case -- either groups not integers or don't have restricted size -- original histogram counting sort can created placing group values in hash-table. hash-table cannot have more n entries, requires o(n) space , expected o(n) time create.

if planning repeatedly shuffle same array, should keep sorted array , copy of histogram, since construction of these auxiliary structures more half time of producing shuffle.