Merge Sort

Merge sort(sometimes spelled mergesort) is an efficientsorting algorithmthat uses adivide-and-conquerapproach to order elements in anarray. Sorting is a key tool for many problems in computer science. For example, inputting a list of names to a sorting algorithm can return them in alphabetical order, or a sorting algorithm can order a list of basketball players by how many points they each scored. Running time is an important thing to consider when selecting a sorting algorithm since efficiency is often thought of in terms of speed. Mergesort runs in a guaranteed \(O(n \log n)\) time, which is significantly faster than the average- and worst-case running times of several other sorting algorithms.

Sorting may seem like a simple concept, but efficient sorting is critical when dealing with large amounts of data. Sorting is the basis for more complex computer programs such as searching for files on a computer, finding the shortest route to a destination, and compressing data.

归并排序有两个步骤:合并和排序。的algorithm uses a divide-and-conquer approach to merge and sort a list.

Divide and conquer is a technique used for breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. It can be helpful to think of this method as divide, conquer, and combine.

的mergesort algorithm focuses on how to merge together two pre-sorted arrays such that the resulting array is also sorted. Mergesort can be implemented eitherrecursivelyor iteratively.

Here is the recursive mergesort algorithm:

1. If the list has only one element, return the list and terminate. (Base case)
2. Split the list into two halves that are as equal in length as possible. (Divide)
3. Using recursion, sort both lists using mergesort. (Conquer)
4. Merge the two sorted lists and return the result. (Combine)

This animation illustrates the procedure described above.

的mergesort function uses the merge function. The purpose of the merge function is to merge two sorted lists such that the resulting list is also sorted.

的Merge Algorithm

Here is one way to implement merge:

1. Create an empty list called the result list.
2. Do the following until one of the input lists is empty: Remove the first element of the list that has a lesser first element and append it to the result list.
3. When one of the lists is empty, append all elements of the other list to the result.

Complexity of Merge

的merge function does a \(O(1)\) (constant) number of operations for each element in the list. The list size is \(O(n)\) since there are \(n\) elements. Merge does a constant amount of work \(O(n)\) times, so merge runs in \(O(n)\) time.

Here is one way to implement mergesort in Python. There are many other implementations of the algorithm, but the ideas behind them are the same. Mergesort can be used to sort any orderable list.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

defmerge(left,right):result=[]left_idx,right_idx=0,0whileleft_idx<len(left)andright_idx<len(right):# change the direction of this comparison to change the direction of the sortifleft[left_idx]<=right[right_idx]:result.append(left[left_idx])left_idx+=1else:result.append(right[right_idx])right_idx+=1ifleft:result.extend(left[left_idx:])ifright:result.extend(right[right_idx:])returnresultdefmerge_sort(m):iflen(m)<=1:returnmmiddle=len(m)//2left=m[:middle]right=m[middle:]left=merge_sort(left)right=merge_sort(right)returnlist(merge(left,right))

Division:
It takes \(O(1)\) time to divide the problem into two parts. To divide the problem, the algorithm computes the middle of the list by taking the length of the list and dividing by two, which takes constant time.

Solving the subproblems:
Two equally large subproblems are produced. Each half takes \(T\left(\frac{n}{2}\right)\) time, so solving the subproblems takes a total of \(2\,T\left(\frac{n}{2}\right)\) time.

Combining the subproblems:
This is the merge step of mergesort. This step takes \(O(n)\) time, as shown in the analysis of the merge algorithm.

的refore, \[ T(n) = 2\,T \left ( \frac{n}{2} \right ) + O(n) .\] Themaster theoremtells us that the solution to thisrecurrenceis \[T(n) = O(n \log n).\] Mergesort runs in \(O(n \log n)\) time in its best case, worst case, and average case. That means that no matter what the input, mergesort will operate in \(O(n \log n)\) time.

Some other sorting algorithms have a faster best-case running time, such asinsertion sort, which runs at best in \(O(n)\) time. However, insertion sort has a worst- and average-case running time of \(O(n^2)\), which is much slower than \(O(n)\) and \(O(n \log n)\). You might choose insertion sort over mergesort if your list is already mostly sorted—insertion sort would take \(O(n)\), while mergesort will still take \(O(n \log n)\). Mergesort is used when we want a guaranteed running time of \(O(n \log n)\), regardless of the state of the input.

归并排序是一种稳定的排序space complexityof \(O(n)\).

Pros

• Time-efficient with time complexity of \(O(n \log n)\)
• Can be used for external sorting
• Highly parallelizable
• Stable sort

Cons

• Marginally slower than quicksort in practice
• Not as space-efficient as other sorting algorithms, e.g. block sort