The problem of interchanging two segments of an array is considered. Using the known methods as a starting-point, two new adaptations are developed that achieve higher memory locality. It is confirmed, both analytically and experimentally, that on a computer with a hierarchical memory the adaptations are superior to the earlier methods.

@inproceedings{BK2000bC,
  author = {Jesper Bojesen and Jyrki Katajainen},
  title = {Interchanging two segments of an array in a hierarchical memory
    system},
  booktitle = {Proceedings of the 4th International Workshop on Algorithm
    Engineering},
  series = {Lecture Notes in Computer Science},
  volume = {1982},
  publisher = {Springer-Verlag},
  year = {2001},
  pages = {159--170},
}