c# - Reorder an IList<T> using the minimum number of Inserts and Removes -

i need extension method takes 2 arguments: target ilist<t> , custom comparer.

public static void customsort<t>( ilist<t> target, icomparer<t> comparer ) {     ... } 

the extension method's job arrange target's elements in order indicated custom comparer.

here solutions won't work:

• the list<t>.sort in-place sorting, i'm after. can't assume target's concrete type list<t>.
• linq offers solutions unfortunately output results new enumerable instead of modifying target list.

instead, need target's remove , insert methods called put elements right order. target list may observable important solution not more removes , inserts necessary obtain desired order.

i think you.

we sort array of offsets, determine set of deltas need applied , apply them produce newly ordered ilist.

public static void customsort<t>( ilist<t> list , icomparer<t> comparer ) {   int[] unsorted = enumerable.range(0,list.count).toarray() ;   int[] sorted   = enumerable.range(0,list.count).orderby( x => list[x] , comparer ).toarray() ;   var   moves    = sorted.zip( unsorted , (x,y) => new{ src = x , dest = y , } ).where( x => x.src != x.dest ).orderby( x => x.src ).toarray() ;    // @ point, moves list of moves, source position destination position.   // enumerate on , apply moves in order.   // need scratch pad save incomplete moves, existing item has   // been over-written, has not yet been moved final destination.    dictionary<int,t> scratchpad = new dictionary<int, t>() ; // parking lot incomplete moves   foreach ( var move in moves )   {     t value ;      // see if source value on scratchpad.     // if is, use , remove scratch pad.     // otherwise, indicated slot in list.     if ( scratchpad.trygetvalue( move.src , out value ) )     {       scratchpad.remove( move.src );     }     else     {       value = list[ move.src ] ;     }      // if destination after source position, need put     // on scratch pad, since haven't yet used source.     if ( move.dest > move.src )     {       scratchpad.add( move.dest , list[ move.dest ]);     }      // finally, move source value destination slot.     list[ move.dest ] = value ;    }    return ; }