private void trSort(int n, int depth)
    {
        final int[] arr = this.sa;
        TRBudget budget = new TRBudget(trIlg(n)*2/3, n);

        for (int isad=n+depth; arr[0]>-n; isad+=(isad-n))
        {
            int first = 0;
            int skip = 0;
            int unsorted = 0;

            do
            {
                final int t = arr[first];

                if (t < 0)
                {
                    first -= t;
                    skip += t;
                }
                else
                {
                    if (skip != 0)
                    {
                        arr[first+skip] = skip;
                        skip = 0;
                    }

                    final int last = arr[n+t] + 1;

                    if (last - first > 1)
                    {
                        budget.count = 0;
                        this.trIntroSort(n, isad, first, last, budget);

                        if (budget.count != 0)
                            unsorted += budget.count;
                        else
                            skip = first - last;
                    }
                    else if (last - first == 1)
                        skip = -1;

                    first = last;
                }
            }
            while (first < n);

            if (skip != 0)
                arr[first+skip] = skip;

            if (unsorted == 0)
                break;
        }
    }