LeetCode’s Sort an Array problem was a push for me to really understand different sorting algorithms. So I decided to implement few sorting algorithms.

Bubble sort

Bubble sort is considered as the simplest sorting algorithm out there. The idea is to scan through an array and swap consecutive elements if they are in word ordered until the array gets sorted. In Java, we have

int[] bubbleSort(int[] a){
  int n = a.length;
  for(int i = n - 1; i > -1; --i){
    for(int j = 0; j < i; ++j){
      if(a[j] > a[j + 1]){
        int swap = a[j + 1];
        a[j + 1] = a[j];
        a[j] = swap;
      }
    }
  }
  return a;
}

The average and worst time complexity is \(O(n^2)\).

Insertion sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. In Java, we have

int[] insertionSort(int[] a){
  int n = a.length;
  for(int i = 1; i < n; ++i){
    int j = i;
    while(j > 0 && a[j - 1] > a[j]){
      int swap = a[j - 1];
      a[j - 1] = a[j];
      a[j] = swap;
      --j;
    }
  }
  return a;
}

In the best case it is \(O(n)\), in average and worst time complexity is \(O(n^2)\).

Selection sort

Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. In Rust, we have

fn selection_sort(a: &mut Vec<i32>){
  let n = a.len();
  for i in 0..n{
    let mut m = i;
    for j in (i+1)..n{
      if a[j] < a[m]{
        m = j;
      }
    }
    a.swap(i,m);
  }
}

The average and worst time complexity is \(O(n^2)\).

Merge sort

Merge sort is a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

Here is one possible merge sort implementation (which does not directly modify the array) in Java:

int[] mergeSort(int[] a) {
  return helper(a, 0, a.length - 1);
}
int[] helper(int[] a, int start, int end) {
  if(start == end){
    return new int[]{a[start]};
  }
  int[] arr = new int[end - start + 1];
  int mid = start + (end - start) / 2;
  int[] arr1 = helper(a, start, mid);
  int[] arr2 = helper(a, mid + 1, end);
  int i1 = 0, i2 = 0, i = 0;
  while (i1 < arr1.length || i2 < arr2.length){
    if(i1 < arr1.length && i2 < arr2.length && arr1[i1] > arr2[i2]){
      arr[i] = arr2[i2];
      ++i2;
    } else if (i1 == arr1.length){
      arr[i] = arr2[i2];
      ++i2;
    } else {
      arr[i] = arr1[i1];
      ++i1;
    }
    ++i;
  }
  return arr;
}

The average time complexity is \(O(n\log(n))\), in worst case also \(O(n\log(n))\).

Quicksort

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.

Here is one possible quick sort implementation in Java:

void quickSort(int[] a){
  helper(a, 0, a.length - 1);
}
void swap(int[] a, int i, int j){
  int tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
void helper(int[] a, int start, int end){
  if(end <= start){
    return;
  }
  int left = start, right = end;
  int pivot = pivotChoose(a, start, end);
  swap(a, pivot, end);
  --right;
  while(left < right){
    while(left < right && a[left] <= a[end]){
        ++left;
    }
    while(left < right && a[right] >= a[end]){
        --right;
    }
    if(left < right){
      swap(a, left, right);
    }
  }
  swap(a, left, end);
  helper(a, 0, left - 1);
  helper(a, left + 1, end);
}
int pivotChoose(int[] a, int start, int end){
  int mid = start + (end - start) / 2;
  if(a[start] > a[mid]){
    swap(a, start, mid);
  }
  if(a[mid] > a[end]){
    swap(a, mid, end);
  }
  if(a[start] > a[mid]){
    swap(a, start, end);
  }
  return mid;
}

The average time complexity is \(O(n\log(n))\), in worst case \(O(n^2)\).