快速排序是一种分治算法，主要通过以下过程进行排序：
选择一个基准元素。
根据基准元素将数组分为两部分：一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
对这两部分递归排序。
快排的最坏时间复杂度为O(n^2)，平均时间复杂度O(n log n)（递归树的高度大约是 log n，每一层的比较次数是 O(n)，因此总体时间复杂度为：O(n log n)）
推导过程：
最坏时间复杂度：
在最坏的情况下划分是非常不平衡的也就是说每次划分的两个子数组是只有 1 个元素的和一个有 n-1 个元素的数组。对于这种情况往往是我们的数组是有序的（或者趋近于有序），或者是我们选取基准值是总是选取当前划分数组的最小值或者最大值。
假设我们每次选择都是选择最小值或者最大值来作为基准值，这样的话每次划分都会划分为一个很小的数组 和 一个非常大的数组：
第一层：划分时，我们比较 n 个元素，时间复杂度为O(n)；
第二层：划分时，我们比较的是 n - 1 个元素，时间复杂度为O(n - 1)；
以此类推，最后一层：划分时，我们比较次数是1；
所以说，总的时间复杂度T(n)为
T(n) = n + n - 1 + n -2 + n -3 + ... + 1 = (n(n-1))/2 = O(n^2)；
归并排序是一种分治算法，它的基本步骤如下：
分解：将待排序的数组分成两半。
解决：递归地对每一半进行排序，直到每个子数组只包含一个元素。
合并：将两个已经排好序的子数组合并成一个有序数组。
为什么归并排序总是 O(n log n)？
归并排序的核心思想是分而治之，每次将一个数组分成两半，并且每一层的合并操作都要遍历整个数组，因此时间复杂度始终是 O(n log n)，无论是最坏情况、最好情况还是平均情况。
比较快速排序和归并排序
快速排序：时间复杂度在最坏情况下可能退化为 O(n^2)，但在最佳和平均情况下，它的时间复杂度是 O(n log n)。
归并排序：无论是最坏、最佳还是平均情况，它的时间复杂度始终是 O(n log n)，但空间复杂度较高，需要 O(n) 的额外空间。
总结
比较排序：归并排序在每个合并步骤中通过比较两个已排序子数组的元素，按顺序将它们合并成一个有序数组。
时间复杂度：每层的合并操作时间复杂度是 O(n)，而递归树的深度是 O(log n)，因此总体时间复杂度是 O(n log n)。
空间复杂度：归并排序需要额外的数组来存储合并后的结果，空间复杂度是 O(n)。