Given a sequence of elements, sorting them means that ordering them in a particular fashion. In general, when we talk about sorting, we are talking about ordering them in ascending order.
Example
Initial Sequence: 3, 4, 1, 6, 2, 5
After Sorting: 1, 2, 3, 4, 5, 6
The values might be integers, or strings, or even other kinds of objects.
The most popular sorting algorithms are:
We covered Bubble Sort, Selection Sort, and, Insertion Sort in the previous tutorial. In this tutorial, we will cover Quick Sort and Merge Sort.
Quick Sort
Introduction
Quick Sort is one of the most popular and efficient sorting algorithms. It is generally the default sorting algorithms in many programming languages (including C++ and Java).
Even though the worst case time complexity of Quick Sort is O(n^2), it works at O(n log n) in most cases and is generally much faster than merge sort if implemented properly.
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Algorithm
- Pick an element, called a pivot, from the array.
- Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
The base case of the recursion is arrays of size zero or one, which are in order by definition, so they never need to be sorted.
There are multiple variants of quick sort depending on the choice of pivot. Some popular choices of pivots being:
- First element of the unsorted array
- Last element of the unsorted array
- Middle element of the unsorted array
- Random element from the unsorted array
The choice of pivot determines the chances of the algorithm hitting the worst case for the given array.
Example
Visualization
Code
C++
int partition (int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
void quickSortUtil(int arr[], int low, int high) {
if (low >= high) {
return;
}
int pivot = partition (arr, low, high);
quickSortUtil(arr, low, pivot - 1);
quickSortUtil(arr, pivot + 1, high);
}
void quickSort(int arr[], int n) {
quickSortUtil(arr, 0, n - 1);
}Java
static int partition (int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
static void quickSortUtil(int arr[], int low, int high) {
if (low >= high) {
return;
}
int pivot = partition (arr, low, high);
quickSortUtil(arr, low, pivot - 1);
quickSortUtil(arr, pivot + 1, high);
}
static void quickSort(int arr[]) {
quickSortUtil(arr, 0, arr.length - 1);
}Complexity Analysis
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n2)
Space Complexity: O(n) for recursion stack.
Merge Sort
Introduction
Merge Sort is also a Divide and Conquer algorithm similar to Quick Sort. The input array right into two parts in the middle. The two haves are then sorted recursively and then merged to create the sorted array.
Algorithm
The algorithm looks something like this:
- Sort the left half of the array
- Sort the right half of the array
- Merge both the halves of the array
The base case of the recursion is arrays of size zero or one, which are in order by definition, so they never need to be sorted.
Example
Visualization
Code
C++
void merge (int arr[], int left, int mid, int right) {
int sizeFirst = mid - left + 1;
int sizeSecond = right - mid;
int firstArr[sizeFirst];
int secondArr[sizeSecond];
for (int i = 0; i < sizeFirst; i++) {
firstArr[i] = arr[left + i];
}
for (int i = 0; i < sizeSecond; i++) {
secondArr[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < sizeFirst && j < sizeSecond) {
if (firstArr[i] < secondArr[j]) {
arr[k++] = firstArr[i++];
} else {
arr[k++] = secondArr[j++];
}
}
while (i < sizeFirst) {
arr[k++] = firstArr[i++];
}
while (j < sizeSecond) {
arr[k++] = secondArr[j++];
}
}
void mergeSortUtil(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left)/2;
mergeSortUtil(arr, left, mid);
mergeSortUtil(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void mergeSort(int arr[], int n) {
mergeSortUtil(arr, 0, n - 1);
}Java
static void merge (int arr[], int left, int mid, int right) {
int sizeFirst = mid - left + 1;
int sizeSecond = right - mid;
int[] firstArr = new int[sizeFirst];
int[] secondArr = new int[sizeSecond];
for (int i = 0; i < sizeFirst; i++) {
firstArr[i] = arr[left + i];
}
for (int i = 0; i < sizeSecond; i++) {
secondArr[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < sizeFirst && j < sizeSecond) {
if (firstArr[i] < secondArr[j]) {
arr[k++] = firstArr[i++];
} else {
arr[k++] = secondArr[j++];
}
}
while (i < sizeFirst) {
arr[k++] = firstArr[i++];
}
while (j < sizeSecond) {
arr[k++] = secondArr[j++];
}
}
static void mergeSortUtil(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left)/2;
mergeSortUtil(arr, left, mid);
mergeSortUtil(arr, mid + 1, right);
merge(arr, left, mid, right);
}
static void mergeSort(int arr[]) {
mergeSortUtil(arr, 0, arr.length - 1);
}Complexity Analysis
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity: O(n)
