mov     x19, x0           // x19 = x0
mov     x2, #0            // x2 = 0

ldr     w5, [x19, x4, lsl #2]  // w5 = *(x19 + x4 * 4)
ldr     w6, [x19, x2, lsl #2]  // w6 = arr[i]

str     w7, [x19, x2, lsl #2]  // *(x19 + x2 * 4) = w7

stp     x29, x30, [sp, #-32]!  // 预索引模式,先sp=sp-32,再存储
ldp     x19, x20, [sp, #16]    // 从sp+16处加载到x19和x20

add     x2, x2, #1        // x2 = x2 + 1 (i++)
sub     x3, x1, #1        // x3 = x1 - 1 (j = n-1)

lsr     x4, x4, #1        // x4 = x4 >> 1 (除以2)

lsl #2                    // 左移2位,相当于乘以4

cmp     x1, #1            // 比较 x1 和 1
cmp     x2, x3            // 比较 i 和 j
cmp     w6, w5            // 比较 arr[i] 和 pivot

ble     L_ret             // 小于等于时跳转 (<=)
b.gt    L_done            // 大于时跳转 (>)
b.ge    L_right           // 大于等于时跳转 (>=)
b.le    L_swap            // 小于等于时跳转 (<=)
blt     L_no_left         // 小于时跳转 (<)

b       L_left            // 无条件跳转到L_left标签

bl      _quicksort        // 调用函数,返回地址保存在X30(LR)

ret                       // 返回到X30(LR)中保存的地址

.text                     // 代码段
.globl _quicksort         // 声明全局符号
.align 2                  // 4字节对齐(2^2=4)

_quicksort:
    // 边界检查
    cmp     x1, #1
    ble     L_ret             // n <= 1 直接返回

    // 建立栈帧
    stp     x29, x30, [sp, #-32]!
    stp     x19, x20, [sp, #16]
    mov     x29, sp

    mov     x19, x0           // 保存数组基址
    mov     x20, x1           // 保存数组长度

    mov     x2, #0            // i = 0
    sub     x3, x1, #1        // j = n - 1

    // 选择中间元素作为pivot
    mov     x4, x1
    lsr     x4, x4, #1        // x4 = n / 2
    ldr     w5, [x19, x4, lsl #2]  // pivot = arr[n/2]

L_left:
    cmp     x2, x3
    b.gt    L_done

    ldr     w6, [x19, x2, lsl #2]
    cmp     w6, w5
    b.ge    L_right           // arr[i] >= pivot
    add     x2, x2, #1
    b       L_left

L_right:
    cmp     x2, x3
    b.gt    L_done

    ldr     w7, [x19, x3, lsl #2]
    cmp     w7, w5
    b.le    L_swap            // arr[j] <= pivot
    sub     x3, x3, #1
    b       L_right

L_swap:
    str     w7, [x19, x2, lsl #2]  // arr[i] = w7
    str     w6, [x19, x3, lsl #2]  // arr[j] = w6

    add     x2, x2, #1
    sub     x3, x3, #1
    b       L_left

L_done:
    // 递归左半部分: [0 .. j]
    mov     x0, x19
    add     x1, x3, #1        // left_len = j + 1
    cmp     x1, #2
    blt     L_no_left
    bl      _quicksort

L_no_left:
    // 递归右半部分: [i .. n-1]
    add     x0, x19, x2, lsl #2   // base = arr + i
    mov     x1, x20
    sub     x1, x1, x2            // right_len = n - i
    cmp     x1, #2
    blt     L_no_right
    bl      _quicksort

L_no_right:

    ldp     x19, x20, [sp, #16]
    ldp     x29, x30, [sp], #32

L_ret:
    ret

ldr w5, [x19, x4, lsl #2]    // *(base + offset * scale)

stp x29, x30, [sp, #-32]!    // sp = sp - 32; *(sp) = x29, x30

ldp x29, x30, [sp], #32      // x29, x30 = *(sp); sp = sp + 32

// 建立栈帧 (函数入口)
stp     x29, x30, [sp, #-32]!   // 1) sp=sp-32  2) 存储FP和LR
stp     x19, x20, [sp, #16]     // 在sp+16位置存储x19,x20
mov     x29, sp                 // 设置当前帧指针

// 清理栈帧 (函数出口)
ldp     x19, x20, [sp, #16]     // 从sp+16恢复x19,x20
ldp     x29, x30, [sp], #32     // 1) 恢复FP和LR  2) sp=sp+32
ret                             // 返回到LR地址

// 计算 arr[i] 的地址 (5条指令)
mov     x10, #4
mul     x11, x2, x10      // x11 = i * 4
add     x12, x19, x11     // x12 = base + offset
ldr     w6, [x12]         // 加载

ldr     w6, [x19, x2, lsl #2]  // 地址计算+加载合并!

#include <stdio.h>

void quicksort(int *arr, int n);

int main() {
    int a[] = {9, 3, 7, 1, 8, 2, 6, 4, 5, 0, 10};
    int n = sizeof(a) / sizeof(a[0]);

    quicksort(a, n);

    for (int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

    .text
    .globl _quicksort
    .align 2

// void quicksort(int *arr, int n);
// x0 = arr
// x1 = n
_quicksort:
    // if (n <= 1) return;
    cmp     x1, #1
    ble     L_ret             // 小于等于 1 直接返回（不建栈帧）

    // 建立栈帧，保存 callee-saved 寄存器
    stp     x29, x30, [sp, #-32]!
    stp     x19, x20, [sp, #16]
    mov     x29, sp

    mov     x19, x0           // x19 = arr base
    mov     x20, x1           // x20 = n

    // i = 0, j = n - 1
    mov     x2, #0            // x2 = i
    sub     x3, x1, #1        // x3 = j = n-1

    // pivot = arr[n/2]
    mov     x4, x1
    lsr     x4, x4, #1        // x4 = n / 2
    ldr     w5, [x19, x4, lsl #2] // w5 = pivot

// ===== 分区循环 =====
// 外层从左扫描开始
L_left:
    // while (i <= j && arr[i] < pivot) i++
    cmp     x2, x3
    b.gt    L_done            // i > j，分区结束

    ldr     w6, [x19, x2, lsl #2]  // w6 = arr[i]
    cmp     w6, w5
    b.ge    L_right           // arr[i] >= pivot，开始从右侧扫描
    add     x2, x2, #1        // i++
    b       L_left

// 从右侧扫描：while (i <= j && arr[j] > pivot) j--
L_right:
    cmp     x2, x3
    b.gt    L_done            // i > j，分区结束

    ldr     w7, [x19, x3, lsl #2]  // w7 = arr[j]
    cmp     w7, w5
    b.le    L_swap            // arr[j] <= pivot，交换
    sub     x3, x3, #1        // j--
    b       L_right

// 交换 arr[i] 和 arr[j]
L_swap:
    // 此时：
    // w6 = arr[i]
    // w7 = arr[j]
    str     w7, [x19, x2, lsl #2]
    str     w6, [x19, x3, lsl #2]

    add     x2, x2, #1        // i++
    sub     x3, x3, #1        // j--
    b       L_left            // 回到从左扫描

// ===== 分区完成，递归两边 =====
L_done:
    // 现在：
    // 左半部分索引范围 [0 .. j]
    // 右半部分索引范围 [i .. n-1]
    //
    // 左长度 left_len = j + 1
    // 右长度 right_len = n - i

    // ---- 递归左半部分 ----
    mov     x0, x19           // base = arr
    add     x1, x3, #1        // left_len = j + 1
    cmp     x1, #2            // 长度 <=1 则不递归
    blt     L_no_left
    bl      _quicksort
L_no_left:

    // ---- 递归右半部分 ----
    add     x0, x19, x2, lsl #2   // base = arr + i
    mov     x1, x20               // n
    sub     x1, x1, x2            // right_len = n - i
    cmp     x1, #2
    blt     L_no_right
    bl      _quicksort
L_no_right:

    // 恢复寄存器 & 返回
    ldp     x19, x20, [sp, #16]
    ldp     x29, x30, [sp], #32

L_ret:
    ret

# macOS (ARM64)
gcc -c qsort.s -o qsort.o
gcc main.c qsort.o -o qsort
./qsort

# 输出: 0 1 2 3 4 5 6 7 8 9 10·