Stalin Sort

Elements that are out of order are simply eliminated. The survivors are sorted. O(n) time, comrade.

0 elements

SpdSize50

>Ready — Stalin Sort

Code

// Stalin Sort: eliminate the disobedient
let lastGood = 0;
for (let i = 1; i < length; i++) {
  if (!compare(lastGood, i)) {
    lastGood = i;
  }
  // out-of-order elements are simply ignored
}

// Stalin Sort: eliminate the disobedient
let lastGood = 0;
for (let i = 1; i < length; i++) {
  if (!compare(lastGood, i)) {
    lastGood = i;
  }
  // out-of-order elements are simply ignored
}

Analysis

BEST O(n)

AVG O(n)

WORST O(n)

SPACE O(1)

STABLE

Stalin Sort iterates through the array once. Any element smaller than the previous one is “purged.” The remaining elements are, by definition, in sorted order. It’s O(n) and technically correct — the best kind of correct. The downside is your array gets shorter. A lot shorter. But the survivors are very well organized.

Edit in playground→