Best way of storing enumerated fields with ability to change order Postgres

Question

What is the best way for storing enumerated fields with ability to change its order? Lets say my database looks like this:

|       Table         |     
|---------------------|
| id |  name  |  order|
| 1  |   1st  |    1  |
| 2  |   2nd  |    2  |
| 3  |   3rd  |    3  |
| 4  |   4th  |    4  |

Now, when user change order in such a away

|       Table         |     
|---------------------|
| id |  name  |  order|
| 1  |   1st  |    1  |
| 4  |   4nd  |    2  |
| 2  |   2nd  |    3  |
| 3  |   3rd  |    4  |

Here I would have to update all rows in this table. I consider 2 solutions

Solution 1)

When inserting row X between for example order 2 and order 3, I would change row's X order field to 3.5, So I would choose number in the middle between adjacent orders. Above table would look like this

|       Table         |     
|---------------------|
| id |  name  |  order|
| 1  |   1st  |    1  |
| 4  |   4nd  |   2.5 |
| 2  |   2nd  |    2  |
| 3  |   3rd  |    3  |

Then, after for example 16 changes I would update table and normalize all order fields, so table after normalization would be like this:

|       Table         |     
|---------------------|
| id |  name  |  order|
| 1  |   1st  |    1  |
| 4  |   4nd  |    2  |
| 2  |   2nd  |    3  |
| 3  |   3rd  |    4  |

Solution 2)

I also consider adding fields "next" (or "next" and "prev") to each row, but it looks for me like waste of memory.

I really dont want to update whole table every time somebody change order. What is the best way of solving this problem?