How to implement merge sort using Python

Merge sort is a classic sorting algorithm. Its core idea is to divide the array to be sorted into several sub-arrays, sort these sub-arrays, and finally merge the sorted sub-arrays into an ordered array. Merge sort is a relatively efficient sorting algorithm with a time complexity of O(nlogn).

In this article, we will explain how to implement merge sort in Python.

1. The idea of ​​​​implementing merge sort

The idea of ​​​​implementing merge sort includes two parts, namely divide and conquer and merge. The specific implementation steps are as follows:

1) Divide the array to be sorted into two parts, and recursively sort the left and right parts;

2) Merge the sorted left and right parts into An ordered array.

2. Use Python to implement divide and conquer

Divide and conquer is the core idea of ​​merge sort. We need to implement the divide and conquer part first.

The code is as follows:

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

In this function, we first determine if the array length is less than or equal to 1, then directly return the array. Otherwise, we need to divide the array into two, recursively sort the left and right parts respectively, and finally merge the sorted left and right parts.

2.1 Implementing Merger

On the basis of dividing and conquering, we need to implement the merged part.

The code is as follows:

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

In this function, we first initialize the pointers i and j, which point to the elements to be compared in the left and right parts respectively. Then we continuously compare the left and right elements, add the smaller element to the result list, and move the pointer to the right. Finally, we also add all remaining elements to the resulting list so that we end up with a sorted array.

3. Complete code

Combining the divide and conquer and merge parts, the complete code is as follows:

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

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

4. Test

In order to verify that our merge sort code is correct, we need to test it.

The code is as follows:

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

The output result is:

[1, 2, 3, 4, 5, 6, 7, 8]

Test The results show that our merge sort code is correct.

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