Let’s have a look at how to how to implement merge sort and quick sort algorithms in python 3. One of the fundamental computer science activities, sorting is essential to many applications. There are many other sorting algorithms, but the two most well-liked ones are Quick Sort and Merge Sort.

Both methods may be used in Python and each has its own special traits, benefits, and drawbacks. In this post, we’ll give a high-level explanation of these algorithms’ operation and go over how to put them into practice in Python. You will have a solid knowledge of how these algorithms operate by the conclusion of this blog and be able to use them to sort data in Python.

Merge Sort

Merge Sort uses the Divide and Conquer strategy. The method divides the input list into two equal parts, sorts each half separately, and then merges the results to produce a sorted output list. The fundamental process that makes Merge Sort effective is the merging stage.

The following stages can be used to summarize the algorithm:

• The input list should be split in half.
• Use Merge Sort to iteratively sort the two parts.
• To create a sorted output list, combine the two sorted halves.

The initial components of each sorted half are compared throughout the merging process, and the smaller element is added to a new list. The procedure is repeated until one of the halves is finished, at which point the last components from the other half are added to the newly created list. To sort the full list, the merging procedure is repeated at each level of recursion.

One of the most effective sorting algorithms is merge sort, which has an O(nlogn) time complexity in the worst, best, and average scenarios. Additionally, Merge Sort maintains the relative order of equal elements in the input list, making it a stable sorting algorithm.

"""
Merge Sort
- Divide and Conquer
- Checks if the size of array > 1
- It divides the array into a left and right array
- Recurses through the array
- While:
 a) Len of left/right counter and len(left/right) array is smaller
 - If: Left element in array < right element in array, add that element
        to the new array.
        -Else add right element
        - Increment new array counter
 - We need to check for left over elements.
  While: length of left/right element < len(left/right array),
        - Add left/right element to new array
        - Increment new array counter
- Return
"""


def merge_sort(array):
    if len(array ) <= 1:
        return array

    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]

    merge_sort(left)
    merge_sort(right)

    l = r = k = 0

    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            array[k] = left[l]
            l += 1
        else:
            array[k] = right[r]
            r += 1
        k += 1

    while l < len(left):
        array[k] = left[l]
        l += 1
        k += 1

    while r < len(right):
        array[k] = right[r]
        r += 1
        k += 1
    return array

Quick Sort

A well-known divide-and-conquer sorting algorithm called Quick Sort divides an array into two sub-arrays depending on a pivot element, recursively sorts each sub-array, and then merges the sub-arrays to generate the sorted output.

The fundamental principle of Quick Sort is to choose an element from the array to act as the pivot, and then divide the array so that all items that are less than the pivot are on one side of it and all elements that are larger than the pivot are on the other. Until the entire array is sorted, this partitioning procedure is applied recursively to each sub-array.

Quick sort python 3 implementation

"""
Quick Sort
- Divide and Conquer
- Check array length >1, else return array
- Works by getting a pivot as the first value of the array
- Defines a lower, equal and greater array
- Loops through the elements in the array
- If element is < pivot, then add it to the lower array
- If element is == pivot, then add it to the equal array
- If element is > pivot, then add it to the greater array
- recurse through the lower array, add the equal element and recurse the larger array

"""

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    lower, equal, greater = [], [], []

    for item in array:
        if item < pivot:
            lower.append(item)
        elif item == pivot:
            equal.append(item)
        else:
            greater.append(item)
    return quick_sort(lower) + equal + quick_sort(greater)

Conclusion

In conclusion, the divide-and-conquer data sorting algorithms Merge Sort and Quick Sort are both effective. Although they adhere to the same concepts, their methods of execution and performance traits vary.

The sorting algorithm Merge Sort delivers stability, dependability, and predictability, with a guaranteed worst-case time complexity of O(n log n). Large dataset sorting in particular benefits from its simplicity of implementation and parallelization.

You might be interested in Implementing Bubble Sort, Insertion Sort and Selection Sort in Python 3