{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiewlxfybk3tfwo3omisntsynhgo4m7zdmqqq4z4ln76ptyaqod7vy",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmtnso53zzx2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.27147v1",
  "publishedAt": "2026-05-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Finn Moltmann",
    "Tamio-Vesa Nakajima",
    "Sebastian Wild"
  ],
  "textContent": "**Authors:** Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild\n\nWe give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption of the algorithm; specifically, for sorting $n$ objects the required buffer area is reduced from space for $n/2$ objects to $O(\\sqrt{n \\log n})$ objects. While this space-efficiency can be achieved (indeed reduced to $O(1)$) conceptually very easily with known inplace merging algorithms, using these as a drop-in replacement for the standard merge algorithm incurs a substantial slow-down. Virtual-Memory Powersort, by contrast, uses the same number of moves and comparisons as previous Powersort implementations up to an additive $O(n)$ term. We report on an empirical running-time study comparing our implementation against other Powersort variants and state-of-the-art stable sorting methods, demonstrating that almost in-place stable sorting can be achieved with negligible overhead in many scenarios.",
  "title": "Virtual-Memory Powersort"
}