基于指定局部操作的n×m二维网格高效排序算法问询

给定一个n×m的网格，指针初始位于(0,0)，仅允许执行以下操作：

• 读取当前单元格及其四邻单元格的值（支持边界环绕）
• 将指针向指定方向移动一格（支持边界环绕）
• 将当前单元格与指定方向的邻元交换值（不支持边界环绕）

请设计符合上述规则的高效算法，使网格的每一行和每一列均按升序单独排序。

示例 #

初始网格为：

4 5 2 2
1 3 6 4

合法的最终排列包括：

1 2 2 3
4 4 5 6

以及

1 2 3 5
2 4 4 6

补充说明 #

我已经实现了一个插入排序版本，但效率较差；如果先单独排序每一行再单独排序每一列，可得到合法结果，其时间复杂度为O(nm² + n²m)——因为插入排序对n个元素的列表时间复杂度为O(n²)，对应代码如下：

def sort_row(direction):
    move(direction)
    for i in range(1, "length of grid in <direction>"):
        val = measure()
        k = i
        while k > 0 and measure(opposite(direction)) > val:
            swap(opposite(direction))
            move(opposite(direction))
            k -= 1
        for _ in range(k, i+1):
            move(direction)

def sort_all_rows(direction):
    for _ in range("length of grid in opposite of <direction>"):
        sort_row(direction)
        move(right(direction))

def sort_rows_then_cols():
    move_to(0, 0)
    sort_all_rows(East)
    sort_all_rows(North)

若能将单行排序的时间复杂度优化至O(n logn)，则整体时间复杂度可达到O(nm log(nm))，这是理论最优复杂度。因此核心问题为：能否实现优于二次时间复杂度的单行排序？

内容的提问来源于stack exchange，提问作者Eknoma