2

I have gigabytes of integers and I want to sort them. How this may be done in haskell without creating a copy of the initial list every iteration?

user3914448
  • 469
  • 1
  • 11
  • 22
  • What "iteration"s are you referring to? – Abhay Feb 15 '15 at 07:09
  • 3
    Relevant: http://en.wikipedia.org/wiki/External_sorting – zerkms Feb 15 '15 at 07:11
  • 1
    You may want to use mutable vectors an in-place sort. Check this answer: http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell – dsign Feb 15 '15 at 08:23
  • is this a trick question from some job interview - from a time when ints where small, so the intended answer was something with bucketsort? – d8d0d65b3f7cf42 Feb 15 '15 at 12:59
  • I'd use an online sorting algorithm such as insertion sort and push stuff through it using conduit. I think that with a little thinking I could manage to merge sort the chunks that conduit would provide to a sink. – Juan Pablo Santos Feb 15 '15 at 18:22

1 Answers1

0

The standard mergesort algorithm in Haskell already doesn't create a copy of the whole list -- it just breaks down the list into chunks and merges those.

The vector-algorithms package (https://hackage.haskell.org/package/vector-algorithms) also provides a number of common and efficient in-place sort algorithms.

sclv
  • 38,665
  • 7
  • 99
  • 204