快速排序和归并排序

快速排序和归并排序应该是基于分而治之思想的最基础的两种排序方法了。它们的相同之处在于处理过程类似，首先把要排序的元素分成两组，然后分别对这两组排序，最后把两组结果合并起来。它们的不同点在于，分组策略不同，因为这的不同，后面的合并策略也不同。

归并排序的分组策略很简单，假设要排序的元素存放在数组中，那么其把数组前面一半元素作为一组，后半一半作为另外一组。

而快速排序呢，根据元素的值来分组，即大于某个值的元素放在一组，而小于的放在另外一组，该值称为pivot。因此在这里，pivot值的挑选很重要，如果太大或太小，那么所有的元素都分在一组了。一般来说，这个值取数组第一个元素的值。

从快速和归并排序来看，先前的分组策略越简单，后面的合并策略就越复杂。因为快速排序本身分组的时候，已经根据元素大小来分组了，合并的时候，只需把两个分组合并起来就行了。而归并排序需要对两个有序的数组根据大小合并。

快速排序代码

quick_sort([H|T]) ->
{L1, L2} = split(H, T),
quick_sort(L1) ++ [H] ++ quick_sort(L2);
quick_sort([]) ->
[].

split(E, [H|T]) when E >= H ->
{F, S} = split(E, T),
{[H|F], S};
split(E, [H|T]) ->
{F, S} = split(E, T),
{F, [H|S]};
split(_, []) ->
{[], []}.

归并排序代码

merge_sort([]) ->
[];
merge_sort([X])  ->
[X];
merge_sort(List) ->
{L1, L2} = lists:split((length(List)+1) div 2, List),
merge(merge_sort(L1), merge_sort(L2)).

merge([H1|T1], [H2|T2]) when H1 =< H2 ->
[H1|merge(T1, [H2|T2])];
merge([H1|T1], [H2|T2]) ->
[H2|merge([H1|T1], T2)];
merge(L1, [])->
L1;
merge([], L2)->
L2.

上面两组代码是Erlang语言写的快速排序和归并排序的代码，从代码上也可以看出，快速排序的主要操作是split，而归并排序的主要操作是merge。

Revisit Quick Sort

quick_sort([]) -> [];

quick_sort([X|Xs]) ->

    quick_sort([Y || Y<-Xs, Y =< X]) + [X] + quick_sort([Y || Y<-Xs, Y>X]).