Python: Sort unsorted numbers using Merge-insertion sort
Python Search and Sorting : Exercise-39 with Solution
Write a Python program to sort unsorted numbers using Merge-insertion sort.
From Wikipedia,
In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson.It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanisław Trybuła and Czen Ping.
Sample Solution:
Python Code:
#Ref.https://bit.ly/3r32ezJ
from __future__ import annotations
def merge_insertion_sort(collection: list[int]) -> list[int]:
"""Pure implementation of merge-insertion sort algorithm in Python
:param collection: some mutable ordered collection with heterogeneous
comparable items inside
:return: the same collection ordered by ascending
Examples:
>>> merge_insertion_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> merge_insertion_sort([99])
[99]
>>> merge_insertion_sort([-2, -5, -45])
[-45, -5, -2]
"""
def binary_search_insertion(sorted_list, item):
left = 0
right = len(sorted_list) - 1
while left <= right:
middle = (left + right) // 2
if left == right:
if sorted_list[middle] < item:
left = middle + 1
break
elif sorted_list[middle] < item:
left = middle + 1
else:
right = middle - 1
sorted_list.insert(left, item)
return sorted_list
def sortlist_2d(list_2d):
def merge(left, right):
result = []
while left and right:
if left[0][0] < right[0][0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result + left + right
length = len(list_2d)
if length <= 1:
return list_2d
middle = length // 2
return merge(sortlist_2d(list_2d[:middle]), sortlist_2d(list_2d[middle:]))
if len(collection) <= 1:
return collection
"""
Group the items into two pairs, and leave one element if there is a last odd item.
Example: [999, 100, 75, 40, 10000]
-> [999, 100], [75, 40]. Leave 10000.
"""
two_paired_list = []
has_last_odd_item = False
for i in range(0, len(collection), 2):
if i == len(collection) - 1:
has_last_odd_item = True
else:
"""
Sort two-pairs in each groups.
Example: [999, 100], [75, 40]
-> [100, 999], [40, 75]
"""
if collection[i] < collection[i + 1]:
two_paired_list.append([collection[i], collection[i + 1]])
else:
two_paired_list.append([collection[i + 1], collection[i]])
"""
Sort two_paired_list.
Example: [100, 999], [40, 75]
-> [40, 75], [100, 999]
"""
sorted_list_2d = sortlist_2d(two_paired_list)
"""
40 < 100 is sure because it has already been sorted.
Generate the sorted_list of them so that you can avoid unnecessary comparison.
Example:
group0 group1
40 100
75 999
->
group0 group1
[40, 100]
75 999
"""
result = [i[0] for i in sorted_list_2d]
"""
100 < 999 is sure because it has already been sorted.
Put 999 in last of the sorted_list so that you can avoid unnecessary comparison.
Example:
group0 group1
[40, 100]
75 999
->
group0 group1
[40, 100, 999]
75
"""
result.append(sorted_list_2d[-1][1])
"""
Insert the last odd item left if there is.
Example:
group0 group1
[40, 100, 999]
75
->
group0 group1
[40, 100, 999, 10000]
75
"""
if has_last_odd_item:
pivot = collection[-1]
result = binary_search_insertion(result, pivot)
"""
Insert the remaining items.
In this case, 40 < 75 is sure because it has already been sorted.
Therefore, you only need to insert 75 into [100, 999, 10000],
so that you can avoid unnecessary comparison.
Example:
group0 group1
[40, 100, 999, 10000]
^ You don't need to compare with this as 40 < 75 is already sure.
75
->
[40, 75, 100, 999, 10000]
"""
is_last_odd_item_inserted_before_this_index = False
for i in range(len(sorted_list_2d) - 1):
if result[i] == collection[-i]:
is_last_odd_item_inserted_before_this_index = True
pivot = sorted_list_2d[i][1]
# If last_odd_item is inserted before the item's index,
# you should forward index one more.
if is_last_odd_item_inserted_before_this_index:
result = result[: i + 2] + binary_search_insertion(result[i + 2 :], pivot)
else:
result = result[: i + 1] + binary_search_insertion(result[i + 1 :], pivot)
return result
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
print("After applying Merge-insertion Sort the said list becomes:")
print(merge_insertion_sort(nums))
print(nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
print("After applying Merge-insertion Sort the said list becomes:")
print(merge_insertion_sort(nums))
print(nums)
nums = [1.1, 1, 0, -1, -1.1, .1]
print("\nOriginal list:")
print(nums)
print("After applying Merge-insertion Sort the said list becomes:")
print(merge_insertion_sort(nums))
chars = ['z','a','y','b','x','c']
print("\nOriginal list:")
print(chars)
print("After applying Merge-insertion Sort the said list becomes:")
print(merge_insertion_sort(chars))
Sample Output:
Original list: [4, 3, 5, 1, 2] After applying Merge-insertion Sort the said list becomes: [1, 2, 3, 4, 5] [4, 3, 5, 1, 2] Original list: [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7] After applying Merge-insertion Sort the said list becomes: [-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178] [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7] Original list: [1.1, 1, 0, -1, -1.1, 0.1] After applying Merge-insertion Sort the said list becomes: [-1.1, -1, 0, 0.1, 1, 1.1] Original list: ['z', 'a', 'y', 'b', 'x', 'c'] After applying Merge-insertion Sort the said list becomes: ['a', 'b', 'c', 'x', 'y', 'z']
Flowchart:
Python Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a Python program to sort unsorted strings using natural sort.
Next: Python Recursion Exercise Home.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics