Comparison-Based Sorts

Previously in this curriculum, you already made quite a few sorts, vastly varying in quality and methodology, but they all had one thing in common. Comparisons, whether you were using the IComparable interface, an IComparer, a delegate of some sort or maybe even some hard-coded check, you sorted items by comparing them to each-other. Now, this comes in quite handy due to its versatility, you can define relationships outside of the sort, and sort any type in any way. Now, the best these sorts can do is O(nLog(n)), which is pretty great, but let's try some linear sorts.

Integer Sorts

First of all, remember hashing? Remember how we used integer hashes as indices in order to access items extremely quickly? Well, we're going to engage in something extremely similar in this section. Now, as the title suggests, we are going to be sorting exclusively with integers/integer keys* in this section, and because of that, we can make a couple assumptions that we are unable to with generic values:

• We can use any key as an index
• We can do whatever math we want on our keys This lets us harness the combined power of fast array operations, and arithmetic (These sorts are all pretty math-y, but nothing too crazy should show up) and get some really neat sorts that are technically linear: O(n)

*While these sorts all rely on integer logic, there is no reason these same algorithms cannot be applied with any data, using integers as keys corresponding to whatever our "value" is weighted as.

<--Previous | Next-->