Introduction

Sorting is arranging an array of N elements in either increasing or decreasing order by some properties. It is very useful in computer science for efficiency in other algorithms that usually require a search.

A stable sort is a sort that can preserve sorting of other properties. For example, if we have:

(3,G), (1,G), (3, A), (6 K), (1,B)

and we want to sort by the first property in increasing order, we will have:

(1, G) (1,B) (3,G), (3,A), (6 K)

If we sort again by the second property we have:

(1,B) (3, A) (1, G) (3, G), (6,K)

then the sort is stable as the first sort is preserved. However, if we sorted differently by the second property and got:

(1,B) (3, A) (3, G) (1, G) (6, K)

then the sort would be unstable.

Slow Sorts

Slow sorts are sorts that have the runtime of O(n2). Although they should almost never be used, it is good to understand how to implement them.

Name Runtime
Bubble Sort O(n2)
Selection Sort O(n2)
Insertion Sort O(n2)

Fast Sorts

Fast sorts are sorts that have a runtime of O(n log n). They are very fast and you will usually use merge sort or quick sort for sorting in the real world. Most language will have their own implementation of a quick sort or merge sort in their standard libraries.

Name Runtime
Heap Sort O(n log n)
Merge Sort O(n log n)
Quick Sort O(n log n)

Super Slow Sorts

Just for fun, these are some silly sorts that you should never use.

Name Runtime
Bozo Sort O(?)
Permutation Sort O(n!)
Miracle Sort O(?)

Exercises

  1. Given two sorted arrays of N numbers, merge the two arrays into an single array of size 2N.
  2. Find the minimum number of swaps to sort an array.
  3. Find the minimum number of adjacent swaps to sort an array.
  4. Let flip(int[] arr, int x) be a function that reverses all elements from arr[0..x]. Devise an algorithm that sorts the array.