{"action":"closed","issue":{"url":"https://api.github.com/repos/ContinuumIO/dask/issues/52","labels_url":"https://api.github.com/repos/ContinuumIO/dask/issues/52/labels{/name}","comments_url":"https://api.github.com/repos/ContinuumIO/dask/issues/52/comments","events_url":"https://api.github.com/repos/ContinuumIO/dask/issues/52/events","html_url":"https://github.com/ContinuumIO/dask/issues/52","id":59036495,"number":52,"title":"Merge sorted sequences of sorted numpy arrays","user":{"login":"mrocklin","id":306380,"avatar_url":"https://avatars.githubusercontent.com/u/306380?v=3","gravatar_id":"","url":"https://api.github.com/users/mrocklin","html_url":"https://github.com/mrocklin","followers_url":"https://api.github.com/users/mrocklin/followers","following_url":"https://api.github.com/users/mrocklin/following{/other_user}","gists_url":"https://api.github.com/users/mrocklin/gists{/gist_id}","starred_url":"https://api.github.com/users/mrocklin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrocklin/subscriptions","organizations_url":"https://api.github.com/users/mrocklin/orgs","repos_url":"https://api.github.com/users/mrocklin/repos","events_url":"https://api.github.com/users/mrocklin/events{/privacy}","received_events_url":"https://api.github.com/users/mrocklin/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-02-26T08:25:34Z","updated_at":"2015-03-11T01:53:45Z","closed_at":"2015-03-11T01:53:45Z","body":"In the near future we may want to implement an [external sort](http://en.wikipedia.org/wiki/External_sorting). One missing piece in our ecosystem is an out-of-core merge sorted operation for sequences of numpy arrays. E.g. given \r\n\r\n1.  A few iterators of sorted numpy arrays in sorted order (e.g. a list of iterables of numpy ndarrays)\r\n2.  An on-disk store supporting numpy setitem syntax (e.g. hdf5, bcolz)\r\n\r\nWe want to walk through each iterator, pull off a numpy array from each, and then perform a merge sorted operation (see [toolz api] (http://toolz.readthedocs.org/en/latest/api.html#toolz.itertoolz.merge_sorted) for example) on these blocks, building up an intermediate block which we periodically push off on to the external store.  In principle this should be almost `O(N)` and probably I/O bound.\r\n\r\nIt is safe to assume that having one block from each of the iterators still fits in memory.\r\n\r\nWe will also need the original index of the values.\r\n\r\nOne approach might be to just use `cytoolz.merge_sorted`.  I assume that this is slower than a straight C/Cython solution operating on binary arrays but it's worth checking out.\r\n\r\nThis seems like the kind of thing that might interest @eriknw @cpcloud @nevermindewe"}}