How to implement merge sort algorithm using Python?

How to implement the merge sort algorithm using Python?

Merge Sort is a common sorting algorithm that uses the idea of ​​divide and conquer to split a large problem into multiple small problems to solve, and then merge the solutions to the small problems. The time complexity of merge sort is O(nlogn) and is suitable for data sets of various sizes.

Below we will introduce in detail how to use Python to implement the merge sort algorithm and give specific code examples.

The basic idea of ​​merge sort is to divide the array to be sorted into two sub-arrays, then sort each sub-array separately, and finally merge the sorted sub-arrays. The specific steps are as follows:

1. Continuously split the array to be sorted into two sub-arrays until each sub-array has only one element. This can be achieved through recursion.
2. Sort each subarray, you can use recursion or iteration.
3. Combine the sorted subarrays to form the final ordered array.

The following is an example code for implementing merge sort in Python:

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

# 测试
arr = [5, 2, 8, 1, 9, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)

The running result is: [1, 2, 3, 5, 8, 9], that is, the array is arranged from small to large Large order.

In the above code, the merge function is used to merge two sorted subarrays. First, we define an empty array result to store the merged ordered array. Then, use two pointers i and j to point to the starting positions of the left subarray and right subarray respectively, and compare the element sizes of the left and right subarrays. If the elements of the left subarray are smaller than the elements of the right subarray, add the elements of the left subarray to the result array, and increase i by 1; otherwise, add the elements of the right subarray Add the result array and increment j by 1. Finally, add the remaining elements in the left subarray or right subarray to the result array. Finally, the merge function returns the merged ordered array.

merge_sortThe function is used for the recursive operation of merge sort. For a given array to be sorted arr, first determine whether the length of the array is less than or equal to 1, and if so, return the array directly. Otherwise, find the middle position of the array via len(arr) // 2 and split the array into two sub-arrays left and right. Then, recursively call the merge_sort function on left and right respectively to merge the two obtained sorted sub-arrays and return the merged ordered array. .

The above are the specific steps and code examples for using Python to implement the merge sort algorithm. I hope it will be helpful for readers to understand the merge sort algorithm.

The above is the detailed content of How to implement merge sort algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!