Skip to Main Content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.
| Brooklyn College Library & Academic IT |CISC Department

CISC 3130 Data Structures: Sorting Algorithms

Professor Chuang Spring 2020 OER


Sorting algorithms perform the operation of turning a collection of elements into ascending order, where items are arranged from smallest value to largest value. 


  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Quicksort
  • Mergesort
  • Shellsort
  • Heap Sort

Bubble Sort


1. Start at position i = 0
2. Compare two pair  i and i+1
3. If A[i] >  A[i+1], swap elements
4. Move pointer one position right.

BubbleSort( int a[])
    int out, in
    for out = a.length-1 to 1
        for in = 0 to out
            if a[in] > a[in+1]
                temp = a[in]
                a[in] = a[in+1]
                a[in+1] = temp
        end for
    end for




1. Divide to find midpoint q. Split input array to [0..q] and [q + 1..n]
2. Conquer by recursively sorting subarrays from first step.
3. Combine by merging the two sorted sub arrays.


mergesort(A, n):   # Sort an array of size n
  mergesort(first half of A, n/2)
  mergesort(second half of A, n/2)
  merge(first half of A, second half of A)

merge (A):

while A not empty or B not empty:
  if first element of A < first element of B:
      remove first element from A
      insert element into C
  end if
      remove first element from B
      insert element into C
end while





Selection Sort

1. Start at position i = 0, find smallest element
2. Swap that with position 0
3. Repeat from position 1 to n, replace next smallest element with position 1 and so on
4. Keep repeating until reaching last position

SelectionSort(int a[])
    for i = 0 to a.length 1
        for j=i+1 to a.length - 1
            if a[j]<a[min]
        end for
        swap a[i] and a[min]
    end for





1. Choose the pivot, store in the rightmost element
2. Partition the array into left (smaller keys) and right (larger keys) groups
3. Call self to sort the left group
4. Call self to sort the right group

5. Merge groups

QuickSort(int a[])
    if start index < end index
        partition list around a pivot
        QuickSort (aLeft[])
        QuickSort (aRight[])






Insertion Sort

1. Marked item is first unsorted
2. Move this element to temporary variable
3. Shift sorted elements until space opens for temporary variable, place in.
4. Repeat with next unsorted item

InsertionSort(int a[])
    int out, in
    for out = 1 to a.length 1
        temp = a[out]
        in = out
        while in>0 and a[in-1]>=temp
            a[in] = a[in - 1]
        end while
        a[in] = temp
    end for




1. Start with max heap
2. Remove root and put into last/vacant place
3. Reduce heap size by 1, heapify
4. Repeat

Heapsort(A) {
  for i <- length(A) downto 1 {
      exchange A[0] <-> A[i]
      heapsize <- heapsize -1
      Heapify(A, 0)

Heapify(A, i) {
  le <- left(i)   ri <- right(i)
  if (le<=heapsize) and (A[le]>A[i])
      largest <- le
      largest <- i
  if (ri<=heapsize) and (A[ri]>A[largest])
      largest <- ri
  if (largest != i) {
      exchange A[i] <-> A[largest]
      Heapify(A, largest)