```python
def mergeSort(L):
    if len(L) > 1:

        mid = len(L)//2

        left = L[:mid]
        right = L[mid:]

        mergeSort(left)
        mergeSort(right)
 
        i = j = k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1
 
        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1
```

Merge Sort (Code)

This algorithm is recursive by nature; it divides the input array into two halves, then merges the two sorted halves. The ```merge()``` function is used for merging two halves.

Pseudocode:
```
# Let the array arr[] be of length n.

1. FInd the middle point to divide the array into two halves. 
middle m = 1 + (n -1) /2

2. Call mergeSort for first half.
mergeSort(arr, 1, m)

3. Call mergeSort for second half.
mergeSort(arr, m + 1, n)

4. Merge the two halves.
merge(arr, 1, m, r)
```


Logic behind Merge Sort

https://www.geeksforgeeks.org/merge-sort/

University of Minnesota - Twin Cities

- Bubble Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Shell Sort
- Radix Sort
- Bitonic Sort
- Bucket Sort
- Quickselect
- Heap Sort

Sorting & Selection Algorithms

https://www.geeksforgeeks.org/bubble-sort/

Bubble Sort

https://www.geeksforgeeks.org/selection-sort/

Selection Sort

Merge Sort

https://www.geeksforgeeks.org/quick-sort/

Quick Sort

Shell Sort

https://www.geeksforgeeks.org/radix-sort/

Radix Sort

https://www.geeksforgeeks.org/bitonic-sort/

Bitonic Sort

https://www.geeksforgeeks.org/bucket-sort-2/

Bucket Sort

A heap is a tree in which items are sorted in a special way. There are two types of heaps: a min-heap and a max heap. A min-heap is one where the parent value is less than the value of the children. A max heap is one where the parent value is greater than the value of the children.

A heap sort algorithm for sorting in increasing order is as follows:
1) Build a max heap from input data
2) Replace the largest item (root) with the last item of the heap and reduce the size of the heap by 1. Then heapify the root of the tree.
3) Repeat step 2 while the size of the heap is greater than 1.

Learn Before

Related

Learn After