What do you mean by "galactic"?

Galactic algorithms have such huge constants they figuratively need a galaxy-sized computer and/or galaxy-sized problem, to have any advantage over the normal solutions. Imagine a generic sorting algorithm in O(n) that had a constant of 10^92 **. Technically superior but in practice unusable.

** Yes, I know that's proven to be impossible.

▲

MichaelDickens 6 hours ago | parent [-]

There are realistic situations where galactic O(n) sorting algorithms exist, right? 32-bit integers can be sorted in O(n) using 2^32 words of memory, using bucket sort[1].

If objects have a maximum size of 4 GB (= 2^35 bits), then arbitrary objects can be sorted in O(n) using 2^2^35 bits of memory.

[1] https://en.wikipedia.org/wiki/Bucket_sort

▲

yyyk 6 hours ago | parent | next [-]

Right, that's why I wrote "a generic sorting algorithm". Your case adds the integer limit which allows it to avoid O(nlogn) minimum.

▲

adrianN 4 hours ago | parent | prev | next [-]

You can use Radix sort https://en.wikipedia.org/wiki/Radix_sort to lower the memory requirement for limited bit-width integers. But there are more practical o(n log n) methods for sorting integers.

	▲	adgjlsfhk1 3 hours ago \| parent [-]
		Well optimized radix sorts are actually pretty fast (assuming you have the proper fallbacks to quicksort/insertion sort to deal with medium/small sizes)

▲

6 hours ago | parent | prev [-]

[deleted]

▲

kite42 7 hours ago | parent | prev [-]

https://en.wikipedia.org/wiki/Galactic_algorithm