Gravity sort, also called bead sort, is a special sorting algorithm. It is not fast at all, but I found the idea is very interesting. Let's see how it works.

Suppose we want to sort numbers [4,3,5,1]. Then we draw a table like below.

x x x x
x x x
x x x x x
x

As you can see, then number of rows stands for number the the array. Number of x in a row stands for the each value in the array. For example, the first value is 4, so the first row has 4 x.

Then suppose we have gravity here, all the x from the top are drawn to the bottom. Then we have a table table like below.

x
x x x
x x x x
x x x x x

Now the table is sorted, naturally. As you can see, the space complexity is O(n*m), while n is the length of the array, m is the max value in the array. The best time complexity is the same. That's why I said before this is not fast at all.

Now let's implement this in code.

function gravitySort(nums: number[]): number[] {

    const max = Math.max(...nums);

    const m: number[][] = Array.from({ length: nums.length }, (_, i) => {
        return Array.from({ length: max }, (_, j) => j < nums[i] ? 1 : 0);
    });

    const move = (i: number, j: number) => {
        while (i < m.length - 1) {
            if (m[i][j] === 1 && m[i + 1][j] === 0) {
                m[i][j] = 0;
                m[i + 1][j] = 1;
            }
            i += 1;
        }
    };

    for (let j = 0; j < max; j++) {
        for (let i = nums.length - 2; i >= 0; i--) {
            move(i, j);
        }
    }

    return m.map(row => row.reduce((prev, cur) => prev + cur));
}

const nums = [4, 3, 5, 1];
const result = gravitySort(nums);
console.log(result); // [ 1, 3, 4, 5 ]