Course Content
Sorting Algorithms
Sorting Algorithms
Merge Sort
You have already discovered intuitive algorithms that sort an array using O(N^2) time. This time is not the limit! Now let's learn advanced and quick algorithms with less Time Complexity than O(N^2).
The first one is a Divide and Conquer recursive algorithm called Merge sort. The main idea is to divide array into two parts, sort them, and then merge these two parts. The algorithm is recursive because parts of array are sorted using Merge Sort function, too.
To see how it works, here is an example.
- Halve the array.
- Sort each part using Merge Sort.
- Merge these two sorted arrays into one.
How to merge? You have two sorted arrays a1 and a2, let’s set pointers p1 and p2 at the beginning of each of them. temp = [] is an array to store the sorted array of elements from a1 and a2. Compare current elements: if a1[p1] < a2[p2], then put a1[p1] to temp and increase p1 by 1. Else do the same for p2.
Merge Example
Algorithm
We have to implement two functions:
mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).
merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.
Time complexity: O(NlogN), and here we need an explanation.
This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?
- To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
- To merge two halves, it takes up to O(N) time.
- Each 'sorting' requires merging, so the total time is O(NlogN).
Space Complexity: O(1).
There is an algorithm:
def merge(arr, m): i, j = 0, m # Pointers at the beginnings of subarrays temp = [] # Merge sorted arrays to temp while i<m or j<len(arr): if i>=m: # Left subarray is empty temp.append(arr[j]) j+=1 elif j>=len(arr): # Right subarray is empty temp.append(arr[i]) i+=1 else: if arr[i] < arr[j]: temp.append(arr[i]) i+=1 else: temp.append(arr[j]) j+=1 return temp def mergeSort(arr): if len(arr) == 1: # Base case return arr m = len(arr) // 2 arr[:m] = mergeSort(arr[:m]) arr[m:] = mergeSort(arr[m:]) return merge(arr, m)
Task
Copy the code of merge() and mergeSort() from the example above or implement it by yourself.
Test this algorithm for given arrays.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Merge Sort
You have already discovered intuitive algorithms that sort an array using O(N^2) time. This time is not the limit! Now let's learn advanced and quick algorithms with less Time Complexity than O(N^2).
The first one is a Divide and Conquer recursive algorithm called Merge sort. The main idea is to divide array into two parts, sort them, and then merge these two parts. The algorithm is recursive because parts of array are sorted using Merge Sort function, too.
To see how it works, here is an example.
- Halve the array.
- Sort each part using Merge Sort.
- Merge these two sorted arrays into one.
How to merge? You have two sorted arrays a1 and a2, let’s set pointers p1 and p2 at the beginning of each of them. temp = [] is an array to store the sorted array of elements from a1 and a2. Compare current elements: if a1[p1] < a2[p2], then put a1[p1] to temp and increase p1 by 1. Else do the same for p2.
Merge Example
Algorithm
We have to implement two functions:
mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).
merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.
Time complexity: O(NlogN), and here we need an explanation.
This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?
- To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
- To merge two halves, it takes up to O(N) time.
- Each 'sorting' requires merging, so the total time is O(NlogN).
Space Complexity: O(1).
There is an algorithm:
def merge(arr, m): i, j = 0, m # Pointers at the beginnings of subarrays temp = [] # Merge sorted arrays to temp while i<m or j<len(arr): if i>=m: # Left subarray is empty temp.append(arr[j]) j+=1 elif j>=len(arr): # Right subarray is empty temp.append(arr[i]) i+=1 else: if arr[i] < arr[j]: temp.append(arr[i]) i+=1 else: temp.append(arr[j]) j+=1 return temp def mergeSort(arr): if len(arr) == 1: # Base case return arr m = len(arr) // 2 arr[:m] = mergeSort(arr[:m]) arr[m:] = mergeSort(arr[m:]) return merge(arr, m)
Task
Copy the code of merge() and mergeSort() from the example above or implement it by yourself.
Test this algorithm for given arrays.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Merge Sort
You have already discovered intuitive algorithms that sort an array using O(N^2) time. This time is not the limit! Now let's learn advanced and quick algorithms with less Time Complexity than O(N^2).
The first one is a Divide and Conquer recursive algorithm called Merge sort. The main idea is to divide array into two parts, sort them, and then merge these two parts. The algorithm is recursive because parts of array are sorted using Merge Sort function, too.
To see how it works, here is an example.
- Halve the array.
- Sort each part using Merge Sort.
- Merge these two sorted arrays into one.
How to merge? You have two sorted arrays a1 and a2, let’s set pointers p1 and p2 at the beginning of each of them. temp = [] is an array to store the sorted array of elements from a1 and a2. Compare current elements: if a1[p1] < a2[p2], then put a1[p1] to temp and increase p1 by 1. Else do the same for p2.
Merge Example
Algorithm
We have to implement two functions:
mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).
merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.
Time complexity: O(NlogN), and here we need an explanation.
This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?
- To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
- To merge two halves, it takes up to O(N) time.
- Each 'sorting' requires merging, so the total time is O(NlogN).
Space Complexity: O(1).
There is an algorithm:
def merge(arr, m): i, j = 0, m # Pointers at the beginnings of subarrays temp = [] # Merge sorted arrays to temp while i<m or j<len(arr): if i>=m: # Left subarray is empty temp.append(arr[j]) j+=1 elif j>=len(arr): # Right subarray is empty temp.append(arr[i]) i+=1 else: if arr[i] < arr[j]: temp.append(arr[i]) i+=1 else: temp.append(arr[j]) j+=1 return temp def mergeSort(arr): if len(arr) == 1: # Base case return arr m = len(arr) // 2 arr[:m] = mergeSort(arr[:m]) arr[m:] = mergeSort(arr[m:]) return merge(arr, m)
Task
Copy the code of merge() and mergeSort() from the example above or implement it by yourself.
Test this algorithm for given arrays.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
You have already discovered intuitive algorithms that sort an array using O(N^2) time. This time is not the limit! Now let's learn advanced and quick algorithms with less Time Complexity than O(N^2).
The first one is a Divide and Conquer recursive algorithm called Merge sort. The main idea is to divide array into two parts, sort them, and then merge these two parts. The algorithm is recursive because parts of array are sorted using Merge Sort function, too.
To see how it works, here is an example.
- Halve the array.
- Sort each part using Merge Sort.
- Merge these two sorted arrays into one.
How to merge? You have two sorted arrays a1 and a2, let’s set pointers p1 and p2 at the beginning of each of them. temp = [] is an array to store the sorted array of elements from a1 and a2. Compare current elements: if a1[p1] < a2[p2], then put a1[p1] to temp and increase p1 by 1. Else do the same for p2.
Merge Example
Algorithm
We have to implement two functions:
mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).
merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.
Time complexity: O(NlogN), and here we need an explanation.
This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?
- To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
- To merge two halves, it takes up to O(N) time.
- Each 'sorting' requires merging, so the total time is O(NlogN).
Space Complexity: O(1).
There is an algorithm:
def merge(arr, m): i, j = 0, m # Pointers at the beginnings of subarrays temp = [] # Merge sorted arrays to temp while i<m or j<len(arr): if i>=m: # Left subarray is empty temp.append(arr[j]) j+=1 elif j>=len(arr): # Right subarray is empty temp.append(arr[i]) i+=1 else: if arr[i] < arr[j]: temp.append(arr[i]) i+=1 else: temp.append(arr[j]) j+=1 return temp def mergeSort(arr): if len(arr) == 1: # Base case return arr m = len(arr) // 2 arr[:m] = mergeSort(arr[:m]) arr[m:] = mergeSort(arr[m:]) return merge(arr, m)
Task
Copy the code of merge() and mergeSort() from the example above or implement it by yourself.
Test this algorithm for given arrays.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowSwitch to desktop for real-world practiceContinue from where you are using one of the options below