I couldn't find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds

```
def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result
```

This question is related to
`python`

`python-3.x`

`algorithm`

`sorting`

`mergesort`

The first improvement would be to simplify the three cases in the main loop: Rather than iterating while some of the sequence has elements, iterate while *both* sequences have elements. When leaving the loop, one of them will be empty, we don't know which, but we don't care: We append them at the end of the result.

```
def msort2(x):
if len(x) < 2:
return x
result = [] # moved!
mid = int(len(x) / 2)
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result
```

The second optimization is to avoid `pop`

ping the elements. Rather, have two indices:

```
def msort3(x):
if len(x) < 2:
return x
result = []
mid = int(len(x) / 2)
y = msort3(x[:mid])
z = msort3(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
```

A final improvement consists in using a non recursive algorithm to sort short sequences. In this case I use the built-in `sorted`

function and use it when the size of the input is less than 20:

```
def msort4(x):
if len(x) < 20:
return sorted(x)
result = []
mid = int(len(x) / 2)
y = msort4(x[:mid])
z = msort4(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
```

My measurements to sort a random list of 100000 integers are 2.46 seconds for the original version, 2.33 for msort2, 0.60 for msort3 and 0.40 for msort4. For reference, sorting all the list with `sorted`

takes 0.03 seconds.

- programming a servo thru a barometer
- Is there a way to view two blocks of code from the same file simultaneously in Sublime Text?
- python variable NameError
- Why my regexp for hyphenated words doesn't work?
- Comparing a variable with a string python not working when redirecting from bash script
- is it possible to add colors to python output?
- Get Public URL for File - Google Cloud Storage - App Engine (Python)
- Real time face detection OpenCV, Python
- xlrd.biffh.XLRDError: Excel xlsx file; not supported
- Could not load dynamic library 'cudart64_101.dll' on tensorflow CPU-only installation
- Upgrade to python 3.8 using conda
- Unable to allocate array with shape and data type
- How to fix error "ERROR: Command errored out with exit status 1: python." when trying to install django-heroku using pip
- How to prevent Google Colab from disconnecting?
- "UserWarning: Matplotlib is currently using agg, which is a non-GUI backend, so cannot show the figure." when plotting figure with pyplot on Pycharm
- How to fix 'Object arrays cannot be loaded when allow_pickle=False' for imdb.load_data() function?
- "E: Unable to locate package python-pip" on Ubuntu 18.04
- Tensorflow 2.0 - AttributeError: module 'tensorflow' has no attribute 'Session'
- Jupyter Notebook not saving: '_xsrf' argument missing from post
- How to Install pip for python 3.7 on Ubuntu 18?
- Python: 'ModuleNotFoundError' when trying to import module from imported package
- OpenCV TypeError: Expected cv::UMat for argument 'src' - What is this?
- Requests (Caused by SSLError("Can't connect to HTTPS URL because the SSL module is not available.") Error in PyCharm requesting website
- How to setup virtual environment for Python in VS Code?
- Pylint "unresolved import" error in Visual Studio Code
- Pandas Merging 101
- Numpy, multiply array with scalar
- What is the meaning of "Failed building wheel for X" in pip install?
- Selenium: WebDriverException:Chrome failed to start: crashed as google-chrome is no longer running so ChromeDriver is assuming that Chrome has crashed
- Could not install packages due to an EnvironmentError: [Errno 13]
- OpenCV !_src.empty() in function 'cvtColor' error
- ConvergenceWarning: Liblinear failed to converge, increase the number of iterations
- How to downgrade python from 3.7 to 3.6
- I can't install pyaudio on Windows? How to solve "error: Microsoft Visual C++ 14.0 is required."?
- Iterating over arrays in Python 3
- How do I install opencv using pip?
- How do I install Python packages in Google's Colab?
- How do I use TensorFlow GPU?
- How to upgrade Python version to 3.7?
- How to resolve TypeError: can only concatenate str (not "int") to str
- How can I install a previous version of Python 3 in macOS using homebrew?
- Flask at first run: Do not use the development server in a production environment
- TypeError: only integer scalar arrays can be converted to a scalar index with 1D numpy indices array
- What is the difference between Jupyter Notebook and JupyterLab?
- Pytesseract : "TesseractNotFound Error: tesseract is not installed or it's not in your path", how do I fix this?
- Could not install packages due to a "Environment error :[error 13]: permission denied : 'usr/local/bin/f2py'"
- How do I resolve a TesseractNotFoundError?
- Trying to merge 2 dataframes but get ValueError
- Authentication plugin 'caching_sha2_password' is not supported
- Python Pandas User Warning: Sorting because non-concatenation axis is not aligned
- [Move to Mergesort with Python]

- Could not load dynamic library 'cudart64_101.dll' on tensorflow CPU-only installation
- Replace specific text with a redacted version using Python
- Upgrade to python 3.8 using conda
- "Permission Denied" trying to run Python on Windows 10
- Python: 'ModuleNotFoundError' when trying to import module from imported package
- What is the meaning of "Failed building wheel for X" in pip install?
- How to downgrade python from 3.7 to 3.6
- I can't install pyaudio on Windows? How to solve "error: Microsoft Visual C++ 14.0 is required."?
- Iterating over arrays in Python 3
- How to upgrade Python version to 3.7?
- TypeError: only integer scalar arrays can be converted to a scalar index with 1D numpy indices array
- How do I resolve a TesseractNotFoundError?
- Could not find a version that satisfies the requirement tensorflow
- Not able to pip install pickle in python 3.6
- json.decoder.JSONDecodeError: Extra data: line 2 column 1 (char 190)
- installing urllib in Python3.6
- pip install returning invalid syntax
- Unable to import path from django.urls
- Display all dataframe columns in a Jupyter Python Notebook
- How to make Firefox headless programmatically in Selenium with Python?
- How to import cv2 in python3?
- Pipenv: Command Not Found
- Error in Python script "Expected 2D array, got 1D array instead:"?
- Fixed digits after decimal with f-strings
- How do I upgrade the Python installation in Windows 10?
- Pip error: Microsoft Visual C++ 14.0 is required
- Python error message io.UnsupportedOperation: not readable
- Anaconda Installed but Cannot Launch Navigator
- Conda command is not recognized on Windows 10
- TypeError: can't pickle _thread.lock objects
- How do you fix the "element not interactable" exception?
- How to print a specific row of a pandas DataFrame?
- Relative imports - ModuleNotFoundError: No module named x
- SyntaxError: unexpected EOF while parsing
- ImportError: No module named 'django.core.urlresolvers'
- Why Python 3.6.1 throws AttributeError: module 'enum' has no attribute 'IntFlag'?
- What is the purpose of "pip install --user ..."?
- Add Legend to Seaborn point plot
- How to install pip for Python 3.6 on Ubuntu 16.10?
- Python sockets error TypeError: a bytes-like object is required, not 'str' with send function
- WinError 2 The system cannot find the file specified (Python)
- Python 3.6 install win32api?
- error UnicodeDecodeError: 'utf-8' codec can't decode byte 0xff in position 0: invalid start byte
- Python 3 - ValueError: not enough values to unpack (expected 3, got 2)
- matplotlib: plot multiple columns of pandas data frame on the bar chart
- Unable to set default python version to python3 in ubuntu
- TypeError: '<=' not supported between instances of 'str' and 'int'
- pandas: merge (join) two data frames on multiple columns
- Replacing a character from a certain index
- Scrolling to element using webdriver?
- [Move to Mergesort with Python]

- How can I tell if an algorithm is efficient?
- Find the smallest positive integer that does not occur in a given sequence
- Efficiently getting all divisors of a given number
- Peak signal detection in realtime timeseries data
- What is the optimal algorithm for the game 2048?
- How can I sort a std::map first by value, then by key?
- Finding square root without using sqrt function?
- Fastest way to flatten / un-flatten nested JSON objects
- Mergesort with Python
- Find common substring between two strings
- Differences between time complexity and space complexity?
- find all subsets that sum to a particular value
- Quicksort with Python
- Insertion sort vs Bubble Sort Algorithms
- What is the fastest way to transpose a matrix in C++?
- What is the difference between dynamic programming and greedy approach?
- How to hash a string into 8 digits?
- Insertion Sort vs. Selection Sort
- recursion versus iteration
- How to check if two words are anagrams
- How can I pair socks from a pile efficiently?
- How do I determine whether my calculation of pi is accurate?
- Efficient way to apply multiple filters to pandas DataFrame or Series
- Difference between Divide and Conquer Algo and Dynamic Programming
- Algorithm to detect overlapping periods
- How to make rounded percentages add up to 100%
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Calculating Waiting Time and Turnaround Time in (non-preemptive) FCFS queue
- Creating all possible k combinations of n items in C++
- Permutations between two lists of unequal length
- Sorting 1 million 8-decimal-digit numbers with 1 MB of RAM
- Python Brute Force algorithm
- Why is the time complexity of both DFS and BFS O( V + E )
- How to find time complexity of an algorithm
- C++: Converting Hexadecimal to Decimal
- From milliseconds to hour, minutes, seconds and milliseconds
- Interview Question: Merge two sorted singly linked lists without creating new nodes
- Finding the median of an unsorted array
- Find running median from a stream of integers
- What exactly does big ? notation represent?
- Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition
- A simple explanation of Naive Bayes Classification
- How can building a heap be O(n) time complexity?
- Evenly distributing n points on a sphere
- Most efficient way to find smallest of 3 numbers Java?
- Find all paths between two graph nodes
- Ukkonen's suffix tree algorithm in plain English
- Generating combinations in c++
- Hash table runtime complexity (insert, search and delete)
- How to compare two colors for similarity/difference
- [Move to Mergesort with Python]

- Sort Array of object by object field in Angular 6
- Sorting a list with stream.sorted() in Java
- How to sort dates from Oldest to Newest in Excel?
- how to sort pandas dataframe from one column
- Reverse a comparator in Java 8
- Find the unique values in a column and then sort them
- pandas groupby sort within groups
- pandas groupby sort descending order
- Efficiently sorting a numpy array in descending order?
- Swift: Sort array of objects alphabetically
- Sort Dictionary by keys
- python, sort descending dataframe with pandas
- Swift how to sort array of custom objects by property value
- Swift Beta performance: sorting arrays
- Finding median of list in Python
- Java 8 stream reverse order
- using lodash .groupBy. how to add your own keys for grouped output?
- lodash multi-column sortBy descending
- What is the difference between `sorted(list)` vs `list.sort()`?
- How to sort a HashSet?
- What is the purpose of shuffling and sorting phase in the reducer in Map Reduce Programming?
- Removing Duplicate Values from ArrayList
- VBA Excel sort range by specific column
- How to sort Counter by value? - python
- Python 3 sort a dict by its values
- How to sort List<Integer>?
- How to sort multidimensional array by column?
- How can I sort a std::map first by value, then by key?
- Sort ObservableCollection<string> through C#
- How to sort an array of objects in Java?
- Mergesort with Python
- How do operator.itemgetter() and sort() work?
- How to sort an ArrayList in Java
- C++ String array sorting
- Quicksort with Python
- sort json object in javascript
- How to sort pandas data frame using values from several columns?
- Python - How to sort a list of lists by the fourth element in each list?
- Insertion sort vs Bubble Sort Algorithms
- How to sort a dataFrame in python pandas by two or more columns?
- orderBy multiple fields in Angular
- How to use Collections.sort() in Java?
- How to sort an ArrayList?
- How to sort 2 dimensional array by column value?
- how to re-format datetime string in php?
- Insertion Sort vs. Selection Sort
- java Arrays.sort 2d array
- Pandas sort by group aggregate and column
- Simple bubble sort c#
- How do I sort a list of datetime or date objects?
- [Move to Mergesort with Python]