ブロックソート
ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えばクイックソートなど)を単純に適用すると文字列の長さ n {\displaystyle n} に対して O ( n 2 log  n ) {\displaystyle \mathrm {O} (n^{2}\log n)} の時間が必要になってしまう。そこで通常は巡回文字列であることを利用して、より効率的なソートを行う。
このためのアルゴリズムは複数提案されており、 O ( n ) {\displaystyle \mathrm {O} (n)} 、 O ( n log  log  n ) {\displaystyle \mathrm {O} (n\log \log n)} 、 O ( n log  n ) {\displaystyle \mathrm {O} (n\log n)} のアルゴリズムが知られているが、実用上は, 自然言語などのような一般的な入力データに対しては O ( n log  n ) {\displaystyle \mathrm {O} (n\log n)} のものが速度やメモリ効率の点で最適である。
bzip2では O ( n log  log  n ) {\displaystyle \mathrm {O} (n\log \log n)} と O ( n log  n ) {\displaystyle \mathrm {O} (n\log n)} のアルゴリズムを入力に応じて最適なものに切り替えて使用している。またブロックサイズは100kバイトから900kバイトまで、-1 ~ -9 オプションで選択でき、デフォルトは900kバイトである。