Optimal reorder algorithm on ordered list

Question

Context

I have an SQL table containing items.

id name  order
==============
1  book  3
2  table 1
3  chair 2
4  bag   4

So as we can see, the items are sorted in this order:

1. table
2. chair
3. book
4. bag

Question

Given a form where a user can reorder an item by selecting another item as reference and a placement (before or after), what is the most optimal algorithm to reorder items so that the order is re-generated from 1 to N (where N is the amount of items)?

By "optimal" I mean consuming the least amount of resources (so the O complexity should be the closest possible to O(N)).

If possible, provide a pseudo-code algorithm (if you prefer writing in your prefered programming language it's fine for me as well).

Example

Here is a picture with the form I intent to use if you need a mental model to better grasp on this challenge:

In action, given this dataset

id name  order
==============
1  book  3
2  table 1
3  chair 2
4  bag   4

Case 1: the user wants to place the bag before the table. The result will be:

id name  order
==============
1  book  4
2  table 2
3  chair 3
4  bag   1

Case 2: Keeping this dataset, the user now decides to place the table after the chair. The result will be:

id name  order
==============
1  book  4
2  table 3
3  chair 2
4  bag   1

Case 3: this time the user would like to place the book before the chair. The result will be:

id name  order
==============
1  book  2
2  table 4
3  chair 3
4  bag   1

Case 4: the user request to put the bag before the chair. The result will be:

id name  order
==============
1  book  1
2  table 4
3  chair 3
4  bag   2

Answer 1

There is not enough space in the comments, so I add one possible solution. This assumes you just use the order column to sort your query and the number itself is of no significance.

Instead of having only the numbers 1 to N in the order column, we can use bigger numbers with gaps. E.g. 100, 200, 300, ... initially. This lets us insert an element before/after another element just by updating a single row.

If we always insert an element in the middle of the gap, then we can calculate the number of modifications you can make in the worst case before having a clash. If there is a clash you need to normalize the order column again before you can do the modification.

Lets have the same initial gap betwen all elements and order[i] is the ith value of the sorted order column, then inital gap size G = order[i + 1] - order[i] - 1. We can calculate the required gap size to ensure we can do M modifications without having to normalize as follows: G(0) = 0 and G(M + 1) = 2 * G(M) + 1. So G needs to be a little bit greater than 2^M. We also need to consider that if we put numbers at the end or the beginning with a gap size of G, then the minimum/maximum of the order column is shrinking/growing G + 1 per modification in the worst case.

Basically the same trick was used by old programmers for languages where you had to number the lines yourself. With the gaps you had space to do modifications later without having to renumber everything.

Answer 2

Quick & dirty solution:

public class MyObj
{
    public int Id { get; set; }
    public int SortOrder { get; set; }
}

private static List<MyObj> Reorder(List<MyObj> list, MyObj first)
{
    //ensure list is sorted by sort order
    list = list.OrderBy(x => x.SortOrder).ToList();

    if (first.SortOrder < 0)
        first.SortOrder = 1;

    if (first.SortOrder > list.Count)
        first.SortOrder = list.Count;

    //get references to the objects
    var firstRef = list.FirstOrDefault(x => x.Id == first.Id);
    var secondRef = list.FirstOrDefault(x => x.SortOrder == first.SortOrder);

    //do nothing if member does not exist or sort order out of range.
    if ((firstRef == null) || secondRef == null || (firstRef.SortOrder == first.SortOrder))
        return list;

    var firstIndex = list.IndexOf(firstRef);
    var secondIndex = list.IndexOf(secondRef);

    //do swap if distance is 1
    if (Math.Abs(firstIndex - secondIndex) == 1)
    {
        (secondRef.SortOrder, firstRef.SortOrder) = (firstRef.SortOrder, secondRef.SortOrder);
        return list;
    }

    //check direction
    var isAsc = firstIndex < secondIndex;

    var backupOrder = !isAsc ? list[Math.Max(firstIndex, secondIndex)].SortOrder : list[Math.Min(firstIndex, secondIndex)].SortOrder;

    if (isAsc)
    {
        firstIndex++;
        secondIndex++;
    };

    //otherwise renumber affected range depending on direction
    var range = list.GetRange(Math.Min(firstIndex, secondIndex), Math.Max(firstIndex, secondIndex) - Math.Min(firstIndex, secondIndex));

    if (isAsc)
        for (int i = 0; i <= range.Count - 1; i++)
        {
            (backupOrder, range[i].SortOrder) = (range[i].SortOrder, backupOrder);
        }
    else
        for (int i = range.Count - 1; i >= 0; i--)
        {
            (backupOrder, range[i].SortOrder) = (range[i].SortOrder, backupOrder);
        }

    firstRef.SortOrder = first.SortOrder;
    return list.OrderBy(x => x.SortOrder).ToList();
}

Usage:

var objList = new List<MyObj>();

for (int i = 1; i < 11; i++)
{
    objList.Add(new MyObj { Id = i, SortOrder = i });
}
//the generated MyObj { Id = 5, SortOrder = 5 } will be moved to SortOrder 2
var reorderedList = Reorder(objList, new MyObj { Id = 5, SortOrder = 2 });

BenchmarkDotNet=v0.13.5, OS=Windows 10 (10.0.19044.2965/21H2/November2021Update), VM=VMware
Intel Xeon Gold 6126 CPU 2.60GHz, 2 CPU, 6 logical and 6 physical cores
.NET SDK=7.0.302
  [Host]     : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2

Method	Mean	Error	StdDev
Reorder	167.0 ns	3.23 ns	3.31 ns