{"issue":{"created_at":"2011-12-11T06:06:55Z","user":{"login":"whoschek","id":919871,"url":"https://api.github.com/users/whoschek","avatar_url":"https://secure.gravatar.com/avatar/ef21c6d32d80c268008f4603db7c0fdc?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","gravatar_id":"ef21c6d32d80c268008f4603db7c0fdc"},"milestone":null,"title":"Use PriorityQueue for k-way merge (perf)","labels":[],"state":"open","updated_at":"2011-12-15T22:55:12Z","id":2514938,"html_url":"https://github.com/cowtowncoder/java-merge-sort/issues/3","closed_at":null,"pull_request":{"patch_url":null,"html_url":null,"diff_url":null},"number":3,"body":"For a k-way merge with k>2 consider using a PriorityQueue instead of multiple 2-way mergers for enhanced performance.","url":"https://api.github.com/repos/cowtowncoder/java-merge-sort/issues/3","comments":5,"assignee":null},"comment":{"created_at":"2011-12-15T22:55:12Z","user":{"login":"whoschek","id":919871,"url":"https://api.github.com/users/whoschek","avatar_url":"https://secure.gravatar.com/avatar/ef21c6d32d80c268008f4603db7c0fdc?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","gravatar_id":"ef21c6d32d80c268008f4603db7c0fdc"},"updated_at":"2011-12-15T22:55:12Z","id":3170577,"body":"I think a java.util.PriorityQueue would work just fine, no? At least that's what we ended up using for our external merge sort impl a few years ago. \n\nBTW, every time you take an entry object from that queue you can reuse it and put it right back into the queue, with a new value from the next item in the input stream. This is to avoid gc issues.\n\nWolfgang.\n\nOn Dec 15, 2011, at 2:38 PM, Tatu Saloranta wrote:\n\n> Ok. So current impl might work well enough, with respect to number of comparisons. Although one could reduce number of calls being made (due to chaining). So maybe I'll still consider binary heap, like adapting https://github.com/simonwrafter/BinaryHeap\n> \n> --- \n> Reply to this email directly or view it on GitHub:\n> https://github.com/cowtowncoder/java-merge-sort/issues/3#issuecomment-3170361","url":"https://api.github.com/repos/cowtowncoder/java-merge-sort/issues/comments/3170577"},"action":"created"}