實現group by最好的辦法？

在SQL和很多函數式的語言(ruby, python...)當中，都可以直接用group_by這樣一個方法(function, method,..). 但是， 如果今天一定要用C, Java, .... 從頭實現， 除了下面的這個思路， 還有沒有更好的？

* 【修改】：input 無序。

* 【修改】：請先不討論Hadoop, MapReduce, ...

Input: [ Key, Value ]

{ [ "A", 1 ], [ "B", 3 ], [ "C", 1 ], [ "A", 2 ], [ "A", 6 ], [ "B", 7 ] ... ... ... }

Output:

{ [ "A", [ 1, 2, 6 ] ], [ "B", [ 3, 7 ] ], [ "C" [ 1 ] ], ... ... }

Output;

for element in "input":

_____for temp in "input":

__________if ( temp.key == element.key )

_______________Output . getKey( element.key ) . addValue( temp.value );

__________end if

_____end for

end for

(以上只是粗略表達一個想法， 沒有仔細考慮細節）

----------------------------------------

* 非常感謝 @vczh 的回答， 排序； 其實我更想知道， 在不能排序下， 有沒有特別漂亮的方法。

* 非常感謝 @鍾穎cyanzhong 的回答， 解釋一下，不排序的原因在於盡量避免修改原數據。 完全同意， 在空間複雜度允許的情況下， 複製數據在排序。

原問題的解法是O(n^2)

@vczh的排序是O(n lg n)