Gọi các thao tác được thực hiện ở bước lẻ là thao tác loại $1$, thao tác được thực hiện ở bước chẵn là thao tác loại $2$.

Ta có nhận xét sau:

• Giả sử ta thực hiện một thao tác loại $1$ đưa phần tử $x$ về vị trí đúng trên mảng, khi đó tất cả các thao tác loại $1$ được thực hiện sau đó sẽ không làm ảnh hưởng đến các vị trí từ $1$ đến $x$.

• Nói cách khác, các thao tác loại $1$ tương đương với việc xác định số lần hoán đổi để đưa phần tử nhỏ nhất về vị trí đầu của mảng, sau đó ta xóa phần tử này đi và thực hiện các thao tác tiếp theo trên mảng mới.

Nhận xét tương tự cho các thao tác loại $2$, ta có thuật toán sau:

• Tại mỗi bước, lưu giữ một mảng $b$ đánh dấu phần tử thứ $i$ trên mảng $a$ chưa bị xóa hay đã bị xóa. Ban đầu $b_i=1$ $(1\le i\le n)$.

• Thao tác loại $1$: Vị trí hiện tại của phần tử $x$ cần sắp xếp trên mảng mới là $b_1+b_2+\dots +b_{po{s}_x}$ $(po{s}_x$ là vị trí của $x$ trên mảng $a$ ban đầu$)$. Số thao tác cần thực hiện để đưa $x$ về vị trí đúng là $b_1+b_2+\dots +b_{po{s}_x}-1$. Sau đó ta đặt $b_{po{s}_x}=0$.

• Thao tác loại $2$: Vị trí hiện tại của phần tử $x$ cần sắp xếp trên mảng mới là $b_{po{s}_x}+b_{po{s}_{x+1}}+\dots +b_n$. Số thao tác cần thực hiện để đưa $x$ về vị trí đúng là $sz-(b_{po{s}_x}+b_{po{s}_{x+1}}+\dots +b_n)$. $(sz$ là kích cỡ hiện tại của mảng sau các thao tác xóa$)$. Sau đó ta đặt $b_{po{s}_x}=0$.

Việc cập nhật và lấy tổng trên một đoạn liên tiếp trên mảng $b$ có thể thực hiện bằng một cây BIT trong $O(log(n))$.

Độ phức tạp: $O(n\times log(n))$