MapReduce是Google提出的一种编程模型，一个处理和生成大数据集的相关实现。本文主要研究了MapReduce平行机排序问题，对极小化最大完工时间(makespan)，论文研究了m台同类机离线和两台机在线排序模型。对极大化最小完工时间，文中研究了同型机离线排序模型。全文共分五章。　　第一章简要地介绍了排序问题的基本知识以及MapReduce的相关知识。　　第二章主要研究m台同类机离线MapReduce排序问题，在这里map任务可以平行加工然而reduce任务不能平行加工。目标是极小化最大完工时间，分别考虑reduce任务可中断和reduce任务不可中断两种情况。对可中断的reduce任务，我们设计了一个近似比为2-s1/∑mj=1sj的算法，其中s1≥s2≥…≥sm，si是机器σi的加工速度;对不可中断的reduce任务，给出了一个近似比为2+√3/3的算法。　　第三章主要研究两台同类机在线MapReduce排序问题，目标是极小化最大完工时间。首先对reduce任务可中断和reduce任务不可中断两种情况，分别给出了问题的下界。对可中断的reduce任务，给出了竞争比为√s2+2s+5+1-s/2的最优算法，其中s是两台机器的速度之比;对不中断的reduce任务，我们证明类似LS算法是最优的且它的竞争比为2s+1/s+1(s＜1+√5/2）和s+1/s（s≥1+√5/2）。　　第四章主要研究离线MapReduce同型机排序问题，目标是极大化最小完工时间。对可中断的reduce任务，给出了3台机的最优算法;对不可中断的reduce任务，考虑2台机、3台机、任意m台机的情况，分别给出了最坏情况界为4/3、3/2、m的近似算法且都是紧的。最后，我们对相关问题的后续研究作了讨论。　　第五章总结全文并提出相关问题进一步的研究方向。