Merge sort implementation

[Scopula]

Specifically, line 40:

result.append((left if left[0] <= right[0] else right).pop(0))

.pop(0) method is O(n) - when you extract the first item you need to shift all remaining items to the left. Because the line is inside the while loop, the merge function is O(n^2).

My benchmark tests support this, using a randomly generated list with 10^5 items:

merge sort time: 1.5746345520019531
new merge time: 0.4434058666229248
sorted time: 0.038704633712768555

"merge sort" is current implementation, "new merge" is my merge sort implementation (using two pointer approach) and "sorted" is just the sorted() built-in function.

I tried to benchmark with 10^6 items, but the current merge sort never completed (waited maybe 15-20 sec).

If I am correct above, then I don't think an O(n log(n)) algorithm should be implemented as O(n^2).

Thank you.

[onlinejudge95]

Though i agree with you, can you share the entire test setup, so that it can be used as a reference for future visitors.
The code you used to measure performance, the code in test etc.

[Scopula]

The test code is at the bottom, I removed the doctests for readability.

As can be seen, with a million items, the current implementation takes around 200 sec, compared to 6 sec with a better implementation.

Here is the output of the tests (slightly formatted):

m@mpc:~/Desktop$ python3 test_merge_sort.py

Testing using an unordered list of 10^4 items:
merge sort time: 0.04936385154724121
better merge sort time: 0.04850363731384277
sorted() time: 0.0028235912322998047

Testing using an unordered list of 10^5 items:
merge sort time: 1.6593587398529053
better merge sort time: 0.4389829635620117
sorted() time: 0.039220333099365234

Testing using an unordered list of 10^6 items:
merge sort time: 208.05022311210632
better merge sort time: 5.504444599151611
sorted() time: 0.5996167659759521

Test code:

# Current implementation.
def merge_sort(collection):
    def merge(left, right):
        result = []
        while left and right:
            result.append((left if left[0] <= right[0] else right).pop(0))
        return result + left + right

    if len(collection) <= 1:
        return collection
    mid = len(collection) // 2
    return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:]))

# A better implementation.
def better_merge_sort(collection):
    def better_merge(left, right):
		# Uses two pointer approach.
		
        len_left, len_right = len(left), len(right)
        i, j = 0, 0
        result = []

        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

        # If there are any items that have not been added at this point, we need to add them.
        for z in range(i, len_left):
            result.append(left[z])

        for y in range(j, len_right):
            result.append(right[y])

        return result

    if len(collection) <= 1:
        return collection

    mid = len(collection) // 2
    left, right = better_merge_sort(collection[:mid]), better_merge_sort(collection[mid:])
    return better_merge(left, right)
	
import random, time

for N in range(4, 7):
	arr = [random.randint(0, 10**5) for _ in range(10**N)]
	
	print(f"Testing using an unordered list of 10^{N} items:")
	
	# Current implementation
	start = time.time()
	res1 = merge_sort(arr)
	time_merge_sort = time.time() - start
	print("merge sort time:", time_merge_sort)
	
	# Better implementation
	start = time.time()
	res2 = better_merge_sort(arr)
	better_merge_sort_time = time.time() - start
	print("better merge sort time:", better_merge_sort_time)
	
	# Sorted(), only used as reference, doesn't use the same algorithm.
	start = time.time()
	res3 = sorted(arr)
	sorted_time = time.time() - start
	print("sorted() time:", sorted_time)

	assert res1 == res3 and res2 == res3

[tegkhanna]

I believe the slicing operation takes O(N/2) time as well. Using start and end pointer will be more meaningful I guess

[github-actions]

Stale issue message

[cclauss]

It would be awesome if someone could create a sort benchmark program that could import each algorithm in our sorts directory and time how long they take to sort at least three payloads:

• short list of ints
• medium tuple of floats
• long generator of str

[onlinejudge95]

@cclauss was there any addition regarding benchmarking? I will pick it up if not