Updating Sort Order

I have a User Interface where user can update the SortOrdr of any products or he can add a new product and can give a user defined sort order.Multiple products can be added and sortorder field is optional. I need to persist the sort order in the database after the user clicks save.So I have listed different scenarios on how sort oder should be updated.I need to write a stable sort or some logic to make sort order unique while persisting.Can you guys tell me where should I start?


Group Name      Product Name      Sort Order(Orginal)      Sort Order(new)    (updated) Sort
Group A            Product 1234                #1                                       #1                             #1
                          Product 1235               #2                                    #2                           #2
                          Product 1236               #3                                    #2                           #3
                          Product 1237               #4                                    #2                            #4


Group Name      Product Name      Sort Order(Orginal)      Sort Order(new)    (updated) Sort
Group A            Product 1234                #1                                       #1                             #1
                          Product 1235               #2                                    #2                           #2
                          Product 1236               #3                                    #2                           #3
                          Product 1237               #4                                    #3                            #4

Group Name      Product Name      Sort Order(Orginal)      Sort Order(new)    (updated) Sort
Group A            Product 1234                #1                                       #1                             #1
                          Product 1235               #2                                    #2                           #2
                          Product 1236               #3                                    #3                           #4
                          Product 1237               #4                                    #4                            #5
                          Product 1238                                                  #3                              #3

Group Name      Product Name      Sort Order(Orginal)      Sort Order(new)    (updated) Sort
Group A            Product 1234                #1                                       #1                             #1
                          Product 1235               #2                                                                    #4
                          Product 1236               #3                                    #2                           #2
                          Product 1237               #4                                                                         #5
                          Product 1238            #5                                   #3                             #3