Overview

Sorting is the process of taking an array of n numbers $A=⟨a_1,a_2,...a_n⟩$ and sorting such that $A^{\prime }=⟨a_1^{\prime },a_2^{\prime },...a_n^{\prime }⟩$ where $a_1^{\prime }\le a_2^{\prime }\le ...\le a_n^{\prime }$. Besides its direct practical applications, using sorting for preprocessing makes many applications much more efficient.

Quick Reference

Search and Sort Complexities:

Techniques

There are two different kinds of sorting techniques, divide and conquer and incremental.

Divide and Conquer

• Divide the problem into one or more subproblems that are just smaller instances of the same problem
• Conquer the subproblems by solving them recursively
• Combine the solutions of each subproblem to form the final solution

Incremental

• Go through each step in the problem one at a time

Bubble Sort

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

Insertion Sort

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

This sort is idea for a small number of elements.

This is similar to sorting a hand of cards:

1. Start with an empty sub-array
2. Insert the first element of the array-to-be-sorted in the sub-array
3. Move to the next element and put it in the correct spot by comparing with each element of the sorted sub-array
4. Continue until the end of the array-to-be-sorted is out of elements

Pseudo Code

# Where A is the array and n is the length of array
def insertionSort(A, n):
	for index = 1 to n: 
		# the key is defined as the first element of the unsorted subarray
		key = A[index]
		previous = index - 1
		# looping through sub-array to find where key goes
		# continue while the previous element is greater than the key and not out of bounds
		while previous > 0 and A[previous] > key:
			# move the previous element up and decrement down the array
			A[previous + 1] = A[previous]
			previous = previous - 1
		# the correct spot for the key is found
		A[previous + 1] = key

Merge Sort

Time Complexity: $O(n\log n)$
Space Complexity: $O(n)$

Merge sort uses the divide and conquer technique.

Pseudo Code

# where p is the first element of the array and r is the last element
def mergeSort(A, p, r)
	if p > r:
		return
	q = (p+r)/2
	mergeSort(A, p, q)

Quick Sort

Time Complexity: $O(n\log n)$
Space Complexity: $O(n)$

Heap Sort

Time Complexity: $O(n\log n)$
Space Complexity: $O(n)$

Reference

1. Sun, Hongyang Various Lectures The University of Kansas 2024

Related

• Algorithms