Merge sorting in python

How To Implement Merge Sort Algorithm In Python

Understand the operations of the merge sort algorithm and how it’s implemented in Python

L earning algorithms can be tedious at times.

The algorithm topic domain is a branch of computer science that has a notorious perception of immense complexity. But algorithms come in different shapes, sizes, and levels of sophistication.

Suppose you aspire to get to a level where you can tackle complex algorithms and solve problems with them. In that case, you have to build a backlog of experience understanding and implementing less complex algorithms.

One of these ‘not too complex’ algorithms is Merge sort.

Here’s what to expect in this article:

• Introduction to divide and conquer approach to problem-solving
• Explanation of the operations and intuitions involved in the merge sort algorithm
• Python implementation of the merge sort algorithm

What Are Divide And Conquer Algorithms?

The Divide and conquer paradigm used in algorithm design incorporates recursion to solve small problems initially derived from a larger problem.

Recursion within the computer science domain is defined as the procedure whereby a function calls itself within its body.

Divide and conquer algorithms are recursive; this means that the initial problem is divided into associated subproblems where a solution can be applied recursively to each subproblem. The final solution to the larger problem is a combination of the solutions to the subproblems.

There are three main components of the divide-and-conquer approach to algorithm design:

1. Divide: continuously break down the larger problem into smaller parts.
2. Conquer: solve each of the smaller parts by utilising a function that’s called recursively.
3. Combine: merge all solutions for all smaller parts into a single unified solution, which becomes the solution to the starting problem.

Источник

Сортировка слиянием: для тех, кто не хочет просто использовать .sort()

Задача, старая как мир. Есть список вещей, который нужно отсортировать. Как это сделать?

Ну, самый интуитивный вариант — взять список, разделить его пополам, затем еще пополам и еще, пока у вас не окажется куча списков с длиной, равной единице. После этого нужно выстроить элементы в пары, располагая их в правильном порядке, а затем соединять эти пары вместе, образуя все большие упорядоченные группы, до тех пор, пока не получите целый отсортированный список. Вам тоже именно это сразу в голову пришло?

Ну ладно, может, это действительно не самое интуитивное решение, но мы избавим вас от утомительного прохождения сортировки пузырьком или случайной сортировки (тут впору вздрогнуть) и сразу перейдем к объяснению сортировки слиянием. Единственное, что вам нужно знать, это что сортировка слиянием по сравнению с другими алгоритмами довольно эффективна. Временная сложность этого алгоритма, как вы можете догадаться по подходу «разделим пополам», — O(N log N).

Итак, давайте начнем. Создадим функцию merge_sort() , которая будет принимать список. Для наших целей мы назовем этот список nums (т. е. «числа»), но тот же метод будет работать со списком любых сортируемых типов, например, со списком строк.

Наш первый шаг — разделить список надвое. Мы будем использовать целочисленное деление, чтобы в итоге получить целый индекс (а то вдруг у нас в списке нечетное количество элементов). Затем мы создадим два меньших списка, left и right . Для этого мы используем очень удобную нотацию Python для подсписков.

Погодите, а если длина списка будет 0 или 1? Мы же тогда не сможем разделить его пополам! Чтобы учесть такую возможность, мы обернем весь наш метод в if-предложение. Таким образом весь этот код будет работать только если длина списка больше 1.

def merge_sort(nums): if len(nums) >1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:]

Что мы делаем дальше? Все просто! Мы отсортируем обе половины, вызывая для них merge_sort() .

def merge_sort(nums): if len(nums) >1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right)

Но погодите, это еще не все. Пока что мы просто последовательно делили наши списки пополам, пока не получили кучу маленьких списков с длиной, равной 1. Например, если бы у нас был список [4, 2, 1, 3] , он был бы разделен на [4, 2] и [1, 3] , а затем на [4] , [2] , [1] и [3] (каждый из этих списков имеет длину, равную 1).

Что дальше? Подсказка кроется в названии алгоритма сортировки. Дальше будет слияние списков.

Здесь нужно быть внимательным. Нам нужно отслеживать три индекса. Назовем их i , j и k . Вот что они будут представлять:

• i — индекс в списке left ,
• j — индекс в списке right ,
• k — индекс в исходном списке nums , в который в конечном итоге нужно вставить все числа по порядку.

Для начала давайте зададим им всем значение 0.

После этого мы будем перебирать и левый, и правый список, сравнивая каждый элемент. Пройти списки необходимо только один раз, потому что left и right уже отсортированы. Нам нужно только соединить их.

Если число из списка left меньше, чем число из списка right , мы вставляем его в nums на позицию k , после чего увеличиваем индекс i на единицу. Если число из списка right меньше или равно числу из списка left , тогда оно отправляется в nums , а мы увеличиваем на единицу индекс j . Наконец, после добавления любого из чисел в список nums , мы увеличиваем на единицу индекс k .

Вот и все! Что касается слияния, мы начали со списков [4] , [2] , [1] и [3] . Эти списки соединились в [2, 4] и [1, 3] , а затем образовали [1, 2, 3, 4] .

Вот наш полный код. Заметьте, что весь метод по сути лежит в самом первом блоке if .

def merge_sort(nums): if len(nums) > 1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: nums[k] = left[i] i+=1 else: nums[k] = right[j] j+=1 k+=1 while i < len(left): nums[k] = left[i] i+=1 k+=1 while j < len(right): nums[k] = right[j] j+=1 k+=1

Проверка

Давайте отсортируем какие-нибудь числа. Создадим список чисел и вызовем для него merge_sort(). Обратите внимание, что мы выводим в результате тот же список nums, потому что наш метод ничего не возвращает, а лишь изменяет исходный список.

nums = [5, 2, 3, 6, 84, 9, 8] merge_sort(nums) print(nums)

В результате вы должны получить отсортированный список — [2, 3, 5, 6, 8, 9, 84] . Как уже говорилось, это сработает и со строками. Если передать этому методу список ['banana', 'apple', 'grape', 'orange'] , он будет отсортирован в алфавитном порядке: ['apple', 'banana', 'grape', 'orange'] .

Метод .sort() в Python работает сходным образом, это тоже алгоритм из серии «разделяй и властвуй», да и временная сложность у него приблизительно такая же. В общем, нет никаких причин, по которым вам стоило бы реализовывать сортировку слиянием… если не вспоминать о технических собеседованиях, конечно. Но теперь-то вы будете готовы к таким заданиям!

Источник

Merge sort in Python

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2023 with this popular free course.

Merge sort is one of the most prominent divide-and-conquer sorting algorithms in the modern era. It can be used to sort the values in any traversable data structure such as a list.

The theory

Merge sort works by splitting the input list into two halves, repeating the process on those halves, and finally merging the two sorted halves together.

The algorithm first moves from top to bottom, dividing the list into smaller and smaller parts until only the separate elements remain. From there, it moves back up, ensuring that the merging lists are sorted.

Implementation

def mergeSort(myList):
 
if len(myList) > 1:
 
mid = len(myList) // 2
 
left = myList[:mid]
 
right = myList[mid:]
 
# Recursive call on each half
 
mergeSort(left)
 
mergeSort(right)
 
# Two iterators for traversing the two halves
 
i = 0
 
j = 0
 
# Iterator for the main list
 
k = 0
 
while i < len(left) and j < len(right):
 
if left[i]  
# The value from the left half has been used
 
myList[k] = left[i]
 
# Move the iterator forward
 
i += 1
 
else:
 
myList[k] = right[j]
 
j += 1
 
# Move to the next slot
 
k += 1
 
# For all the remaining values
 
while i < len(left):
 
myList[k] = left[i]
 
i += 1
 
k += 1
 
while j < len(right):
 
myList[k]=right[j]
 
j += 1
 
k += 1
 
myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)
 

• The list is divided into left and right in each recursive call until two adjacent elements are obtained.
• Now begins the sorting process. The i and j iterators traverse the two halves in each call. The k iterator traverses the whole lists and makes changes along the way.
• If the value at i is smaller than the value at j , left[i] is assigned to the myList[k] slot and i is incremented. If not, then right[j] is chosen.
• This way, the values being assigned through k are all sorted.
• At the end of this loop, one of the halves may not have been traversed completely. Its values are simply assigned to the remaining slots in the list.

And with that, the merge sort has been implemented!

Time complexity

The algorithm works in O(nlogn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.

Источник