データの分析、グラフ作成、および通信のためのツールを備えた Microsoft 表計算ソフトウェアのファミリ。
ooi15000さん、こんにちは。
Windows 10 + Excel 2013 32bit 版で 16000行ぐらいの住所を含む大きめのデータ (約8MB)で確認しましたが、ソートは一瞬で終わりましたので、30分は遅いと思います。
既存ファイルのデータが入力されている範囲を全選択してコピーし、新規ファイルに「値として貼り付け」を行って、新規ファイルとして作り直してみるとどうでしょうか。
以下の記事も参考になさってみて下さい。
・Excel のパフォーマンス-パフォーマンスの問題を最適化するためのヒント | Microsoft Docs
また、パソコンのメモリ容量や CPU の性能にも左右されると思いますが、以下の記事などを参考に、パソコンのクリーンアップなどを行ってみてはいかがでしょう。