这个集合可能已经存储在计算机的随机存储器（RAM）中，当然也有可能只是存储在文件系统的某个文件上，而文件系统通常叫做二级存储器。这个数据集合也有可能被存档在一个第三级的存储器上，此时在存储器上寻找数据就需要额外的处理时间。而且，这些数据在处理之前需要复制到第二级存储器上。第三级存储器一般包括磁带和光学光碟柜。
数据在随机存储器上一般以两种形式保存：基于指针的存储和基于值的存储。假设有人想排序"eagle"、"cat"、"ant"、"dog"和"ball"这些字符串。使用基于指针的存储，如图4-2所示，一个数组（图中连续的方块）包含了指向实际信息（椭圆中的字符串）的指针，而不是直接将信息存储在数组元素的存储空间里面。使用这种方式，我们能够灵活地存储和排序任意复杂结构的数据。
图 4-2 使用指针排序相反地，基于值的存储将n个元素的数据集合打包存储在固定大小的记录块中，这个固定大小定为s（这种方法比较适合于第二级或者第三级存储器）。图4-3表示了如何使用每个大小为5字节的连续存储块来存储图4-2中的数据。在这个例子中，我们处理的数据是字符串，不过同样也可以是其他的结构化的基于记录的信息。“¬”字符表示字符串的结束。在编码中，长度为s的字符串并不包含终止字符。这个字符串集合中的字符串是紧挨着的，并且可以看做是一个一维的数组B[0,n*s)。注意，B[r*s+c]表示第r个单词的第c个字符（c≥0，r≥0），同样的，这个数据集合的第i个元素（i≥0）是子序列B[i*s,(i+1)*s)。
图 4-3 基于值的排序在第二级存储器上存储的信息一般都是基于值的连续字节集合。在第二级存储器上保存一个整数值来表示指针，指向一个有序集合存在磁盘文件的偏移量是可行的。本章将要介绍的算法也能够对磁盘上的数据进行排序，只需要简单地实现在磁盘文件之间交换字节的函数即可。但是，因为对第二级存储器的存取操作会增加很多输入输出请求，性能将会大幅下降。
无论是基于指针的存储还是基于值的存储，一个排序算法都使得数据（在两种情况下，方框均表示数据本身）变得有序。为了简单起见，即使是使用基于值的存储时，我们都将使用A[i]来表示第i个元素。