CODEWITHSUNDEEP
algorithmsortingcomputer-science
Vladimir Ignatev
Vladimir Ignatev

Reputation: 2176

Sorting algorithms with "tight" upper bound by memory

What sorting algorithms exist (if any) having the following properties?

Upvotes: 0

Views: 176

Answers (1)

templatetypedef
templatetypedef

Reputation: 372794

What you're looking for here are external sorting algorithms. The basic model behind an external sorting algorithm is the following: you have a collection of items to sort that's too large to fit into main memory, and those items can be streamed into and out of memory. The goal is to sort all the items. There are many algorithms that work well here:

  • Mergesort can be adapted to work as an external sorting algorithm. Stream the data into main memory, breaking it apart into strands of values that already appear in sorted order. Then, stream those strands into memory in pairs, merging them together and writing the merged sequence to a resulting file. Repeating this process until all the strands are unified gives back a sorted sequence, and the total runtime matches the original mergesort runtime of O(n log n).

  • Quicksort can be adapted to work externally as well. Stream all the items into main memory and pick one of them as a pivot (possibly randomly, or possibly by picking a sample of elements and using its median as the pivot). Then, stream objects into memory a second time to partition the elements into smaller elements and larger elements. Repeating this process will eventually sort the items, though (probably) not as quickly as mergesort.

  • Counting and radix sort can also work well here. Stream your items into memory and distribute them into buckets based on their value (first digit, for example), then recursively sort those buckets further.

This isn't an exhaustive list and there are probably much better algorithms out there, but hopefully it's a good first step in exploring more.

Upvotes: 3

Related Questions