为什么归并排序最坏情况下的运行时间为O（n log n）的？

本文介绍了为什么归并排序最坏情况下的运行时间为O（n log n）的？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有人能向我解释，在简单的英语或一个简单的方法来解释它？

Can someone explain to me in simple English or an easy way to explain it?

推荐答案

在传统的归并排序，每次通过数据加倍排序小节的大小。第一遍之后，该文件将被分类到长度的两个部分。第二遍后，长度为4。然后8，16，等等直至文件的大小。

On a "traditional" merge sort, each pass through the data doubles the size of the sorted subsections. After the first pass, the file will be sorted into sections of length two. After the second pass, length four. Then eight, sixteen, etc. up to the size of the file.

这是需要保持排序节的规模扩大一倍，直到有一个部分包括整个文件。这将需要lg的截面尺寸（N）的倍增到达文件的大小，以及数据的每遍需要时间成比例的记录数

It's necessary to keep doubling the size of the sorted sections until there's one section comprising the whole file. It will take lg(N) doublings of the section size to reach the file size, and each pass of the data will take time proportional to the number of records.