1. Ordering
Merge-SORT is an effective sorting algorithm based on merge operation. This algorithm adopts the classic divide-and-conquer strategy (dividing-and-conquer method divides the problem into some small problems and then recursively solves it, while the conquer stage "fixes" the answers obtained from the divided stages together, that is, divides and conquers), merges the ordered subsequences to obtain a completely ordered sequence; that is, make each subsequence first order, and then makes the subsequence segments order. If two ordered tables are merged into one ordered table, it is called two-way merge.
2. The basic idea of merger and sorting
The sequence to be sorted R[0…n-1] is regarded as n ordered sequences of length 1, and the adjacent ordered lists are merged into pairs to obtain n/2 ordered tables of length 2; these ordered sequences are merged again to obtain n/4 ordered sequences of length 4; if this is repeated, finally a ordered sequence of length n is obtained
3. Algorithm description of merge sorting
Step 1: Apply for space to make its size the sum of two sorted sequences, which is used to store the merged sequences
Step 2: Set two pointers, the initial position is the starting position of the two sorted sequences respectively
Step 3: Compare the elements pointed to by the two pointers, select relatively small elements and put them into the merge space, and move the pointer to the next position
Repeat step 3 until a pointer exceeds the end of the sequence and copy all the remaining elements of the other sequence directly to the end of the merge sequence.
There are two things to do in ordering:
(1) "Decomposition" - divide the sequence into half each time (recursively implement)
(2) "Merge" - merge the divided sequence segments and sort them in two and two.
How to merge?
During each merge, two ordered sequence segments are merged and then sorted.
These two ordered sequence segments are R[low, mid] and R[mid+1, high], respectively.
First merge them into a local temporary array R2, and then copy R2 back to R after the merge is completed.
We call R[low, mid] the first paragraph and R[mid+1, high] the second paragraph.
Each time, take a record from the two segments for keyword comparison, put the smaller one into R2, and finally copy the rest of each segment directly into R2.
After this process, R2 is already an ordered sequence, and then copy it back to R, and the merge and sorting are completed in one go.
4. Code implementation process (python)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Find the intermediate index L = arr[:mid] # left half R = arr[mid:] # Right half
merge_sort(L) # Recursively sort the left half merge_sort(R) # Recursively sort the right half
# Merge two ordered arrays i = j = k = 0
# Copy data to temporary array L[] while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining data in the left half while i < len(L):
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining data in the right half while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Test codearr = [12, 11, 13, 5, 6, 7]
print("Unsorted array:", arr)
merge_sort(arr)
print("Sorted array:", arr)In this example, the merge_sort function first finds the intermediate index of the array, then divides the array into two parts, and sorts these two parts recursively. Finally, use a loop to combine the sorted two arrays into an ordered array.
This is the end of this article about python merge sorting. For more related python merge sorting content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!