Two issues:

• It's not stable, for example mergesort([1, 1.0]) returns [1.0, 1]. Stability is desirable, and you could easily achieve it by using <= instead of <.

• If the given list has more than one element, you return a new list. But if not, then you return the given list. That's inconsistent and dangerous, might trick someone into thinking you return a separate list, and then getting a problem when you don't.

And it's a simple algorithm, but I can barely see it because of the long and unusual variable names. I feel like I'm looking at a wall of characters. I'd use standard single letter names:

def merge(A, B): merged = [] i = j = 0 while i < len(A) and j < len(B): if A[i] <= B[j]: merged.append(A[i]) i += 1 else: merged.append(B[j]) j += 1 merged += A[i:] or B[j:] return merged 

(I also shortened the part after the loop.)

And here's another way to make it faster, using a for loop for one of the inputs:

def merge(A, B): merged = [] j = 0 for a in A: while j < len(B) and B[j] < a: merged.append(B[j]) j += 1 merged.append(a) merged += B[j:] return merged 

Or instead of j < len(B), we can make sure the last element comes from B (this modifies the merge inputs and assumes they're not empty, which is fine within the context of the mergesort function):

def merge(A, B): merged = [] if B[-1] < A[-1]: B.append(A.pop()) j = 0 for a in A: while B[j] < a: merged.append(B[j]) j += 1 merged.append(a) merged += B[j:] return merged 

Times for sorting 10000 random numbers using our various merge functions:

 31.7 ± 0.5 ms merge_yours 31.8 ± 0.4 ms merge_my_first 23.0 ± 0.5 ms merge_my_second 17.3 ± 0.3 ms merge_my_third 

Full code hidden in HTML comment here.

Attempt This Online!

Besides the optimisations which others have already suggested, you could also optimise your code by going beyond the standard merge sort algorithm.

A simple way to make your merge sort a bit more time-efficient is to turn it into a hybrid sorting algorithm, for example. For very small lists, the recursive function calls performed by merge sort can cause some unnecessary overhead. Some other non-recursive sorting algorithms, such as insertion sort, can be faster than merge sort on very small lists.

To implement a simple hybrid sorting algorithm based on merge sort, you can fix a threshold t for the length of the input list. If the length of the list is above the threshold t, you perform the standard split, recursive call, and merge as with merge sort, and if the length of the list is below the threshold, you just sort the list directly, using insertion sort. You might have to play around with different values for the threshold in order to get a function which performs better than the standard merge sort.

You could then also try implementing Timsort, a slightly more sophisticated hybrid algorithm which combines elements of merge sort and insertion sort, and which is used in the built-in sorted method in Python. Your implementation will likely not be as fast as the built-in implementation, but should still be faster than standard mergesort.

Layout

Code is easier to read when there is whitespace around operators. The black program can be used to automatically reformat the code for readability.

It is common to omit the parentheses in if conditions like this:

 if(left[l_idx] < right[r_idx]): 

black also helps with that.

Naming

The PEP 8 style guide recommends snake_case for function and variable names.

mergesort would be merge_sort.

It is common practice for array variables to be plural nouns. Also, the name A is not very descriptive. For example, if the array is a list of numbers, numbers would be better.

left could be lefts, and right could be rights.

sortedArray could be sorted_numbers.

Documentation

The PEP-8 guide also recommends adding docstrings and functions. It would be good to describe the input variable types as well as the return type. It would also be good for mergesort to mention that it is called recursively.

DRY

len(left) is repeated twice. It would be better to assign this to a variable before the while loop. This should be more efficient as well since you don't need to call len every time the while condition is evaluated. len(right) should also be assigned to a variable for efficiency.

Currently, the merge loop checks both indices before each iteration.

• Initially, neither is "at the end".
• The loop body changes only one: check this value.
  When at end of the corresponding part, handle what's left of the other and return.

lint

 sortedArray = [] 

PEP 8 asks that you spell it sorted_array.

Similarly, in the capitalized def mergesort(A):, prefer lowercase (a).

complexity

def mergesort(A): ... left, right = mergesort(A[:middle]), mergesort(A[middle:]) 

Please understand that slicing is expensive here. That is, you're making a copy of the entire array.

Better to create some class MergeSort: with a self.a array that might have a million entries, and pass around a single reference to the array.

Or if you stick with a fortran-style function, use a signature like

def mergesort(a: list[float], start_idx: int, end_idx: int):