>>904 では安定という要求を満たせないので

fruits.each.with_index.sort {|a,b|
(b[0][0] <=> a[0][0]).nonzero? || a[1] <=> b[1]
}.map(&:first)

とか。

もっとスマートに出来そうだけど。