Sắp xếp trộn sửa trực tiếp dãy

```python def mergeSort_into(A, left, right): if left < right: mid = (left + right) // 2 mergeSort_into(A, left, mid) mergeSort_into(A, mid + 1, right) merge_into(A, left, mid, right) ``` Gọi mergeSort_into(A,0,len(A)−1). Đoạn trái gồm left…mid; đoạn phải gồm mid+1…right. Cả hai đều tính cả biên. Sau khi hai lời gọi đã sắp xếp xong các đoạn, merge_into trộn và ghi lại đúng vùng đó. Cơ sở left>=right không làm gì; hàm sửa trực tiếp A và không trả một dãy kết quả. Vì vậy không gán A=mergeSort_into(...).

```python def merge_into(A, left, mid, right): # Hai đoạn đã sắp xếp; dãy phụ chỉ lớn bằng đoạn đang trộn. B = [0] * (right - left + 1) i, j, k = left, mid + 1, 0 while i <= mid and j <= right: if A[i] <= A[j]: B[k] = A[i] i += 1 else: B[k] = A[j] j += 1 k += 1 while i <= mid: B[k] = A[i] i += 1 k += 1 while j <= right: B[k] = A[j] j += 1 k += 1 A[left:right + 1] = B ``` Dãy phụ B có right−left+1 chỗ. i,j chạy theo chỉ số gốc trong A; k chạy từ 0 trong B. Khi trộn xong, A[left:right+1]=B ghi lại đoạn gồm cả right, không đổi phần nằm ngoài đoạn. Bản này sửa A nhưng **vẫn dùng dãy phụ**; không gọi là chỉ cần bộ nhớ hằng số. Việc tạo dãy phụ theo độ dài đoạn đang trộn giúp mỗi bước trộn có công việc tuyến tính theo đoạn ấy.