# Gravity Sort

·

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 ]
``````