The concept of self-organizing lists has its roots in the idea of activity organization of records in files stored on disks or tapes.
[2] John McCabe gave the first algorithmic complexity analyses of the Move-to-Front (MTF) strategy where an item is moved to the front of the list after it is accessed.
He made the conjecture that in the average case, transposition worked at least as well as MTF in approaching the optimal ordering of records in the limit.
[4] McCabe also noted that with either the transposition or MTF heuristic, the optimal ordering of records would be approached even if the heuristic was only applied every Nth access, and that a value of N might be chosen that would reflect the relative cost of relocating records with the value of approaching the optimal ordering more quickly.
Further improvements were made, and algorithms suggested by researchers including: Rivest, Tenenbaum and Nemes, Knuth, and Bentley and McGeoch (e.g. Worst-case analyses for self-organizing sequential search heuristics).