How to properly organize the sorting of elements while maintaining their positions in the database?

Question

JavaScript

Good day to all. I can not solve the problem with the organization of sorting on the site. Or rather, with its correct preservation of the positions of the elements.
I use UI Sortable, in the update method I pass a new index of the element to the script with ajax and save it for this element in the database.
The problem is that it is also necessary to create new elements, and what index should be assigned to them?
Let's say we have elements:

Element 1 (index 1)
Element 2 (index 2)
Element 3 (index 3)
Element 4 (index 4)

What index should we assign to the new element? And what to do with elements that have the same indexes? After all, you can move one element to the second position and the other too. Hence they will both have index 2 and what is the correct way to sort them?
And if you assign the number of all elements as an index and add one, then later such elements may be sorted incorrectly. For example, there were 5 elements, a new one was added with index 6. Two elements were removed and another one was added. The new one is added with index 5. It will come before the last one, which is wrong.

In general, it is interesting how you would implement sorting with preservation. Or how implemented, if already implemented?
It is necessary to store all elements separately with their indexes. Storing an array separately with element indices is not appropriate.

Answer 1

I added the Laravel tag, since I applied my own solution on it, and I post it:
I send the list of elements to the backend like this:
And the elements look like this:

<ul id="#sortable">
    <li data-id="5">Item 1</li>
    <li data-id="6">Item 2</li>
    <li data-id="9">Item 3</li>
</ul>

5,6,9 are the item IDs in the database.
As a result, it comes to the backend like this:
Accordingly, the element key is an index.
I process it like this:

$elements = Elements::where('user_id',$user_id)->get();
foreach($request->input('sort') as $k => $v)
    $rules['sort.'.$k] = 'required|integer';
$validation = Validator::make($request->only('sort'), $rules);
if($validation->passes()) {
    foreach($elements as $k => $v) {
        $sort_id = array_search($v['id'], $request->input('sort'));
        if($sort_id && $v['sort'] != $sort_id) {
            $v['sort'] = $sort_id;
            $v->save();
        }
    }
} else {
    abort(400);
}

Answer 2

1) When using UISortable, indexes will not be repeated if an array of elements is serialized. The widget has a tool for this.
2) When you create a new element, the first step is to check the correctness of the received data, then pull out the maximum index from the database, taking into account the current branch, if it is a tree, then add it to the database with this index + 1. The query will look something like this:
Actually, that's all.