system
Given the following post, respond as if you're commenting on Reddit:
human
ELI5:Cubesort

How does cubesort work? I was reading about other sorting algorithms when I came across Cubesort, and I can't wrap my head around it. I know how other sorting algorithms such as Quicksort, Radix sort and Mergesort work.
gpt
A standard balanced binary search tree (let’s say of numbers) has a root node (avalue at the very top of the tree that should be directly in the middle of our sorted data) with two branches. You compare your key to the root and go from there if it’s higher or lower. You keep comparing until you find your exact key or nothing. Each comparison cuts your search space in half. (O(log(n)) average time for non-ELI5)

Cubesort is a two-dimensional array of arrays, so like a grid where each square is a hole you can put your numbers in. Say we use a 4x4 grid, or 16 holes. Your key is used on the x-axis to determine which column we can find it in. Then it is used on the y-axis to find the specific square. Within that slot (remember, grid of holes) is where we will find what we are looking for, if the value exists. In here is also approximately 4 sorted values to look at. Overall, 6 lookups for 64 spots (or O(log(n)))

Why is this better than our binary search tree? We don’t need to keep pointers to the various branches all over the place. Some operations are also quicker (O(log(cube-root(n))) instead of O(log(n)) for a less ELI5).