線形リストのソートは結構めんどくさいので、できればやらずにすむのが理想。
最初からデータをソート済みの形で保持する構造を使うほうがよい結果が出ることが多い。
二分木構造とかを使うのが普通（実用上、赤黒木になるかな）
でもどうしても線形リストをそのままソートしたいのであれば、
まさにそのような目的のために考案された「マージソート」を使うといい。
http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88
http://www.geocities.jp/ky_webid/algorithm/021.html