Merge Sort Algorithm

Input:

Sequence <A1', A2', ...An'> of numbers

Output:

Permutation of numbers <A1',A2',...An'>

Pseudocode:

Merge Sort (Recursive sorting)

  1. IF n=1, DONE //already sorted
  2. Recursively sort 
    1. A[1,...(n/2)]              AND
    2. A[(n/2)+1,...n]
  3. Merge two sorted list (Subroutine)

 

Description:

Merge sort is a recursive algorithm. It works as follows.

  1. Divides the array into two part and then merge them back. 
  2. Each half will again perform #1 (until there are only two elements remaining)

 

Running Time:

O(n)

Worst Case:

O(n log(n))

Avarage Case:

O(n log(n))


Insertion Sort Algorithm

Input:

Sequence <A1', A2', ...An'> of numbers

Output:

Permutation of numbers <A1',A2',...An'>

Pseudocode:

Insertion Sort(A1n) //Sorts A[1...n]

FOR j <-- 2 to n

DO key <-- A[j]

i<-- j-1

WHILE i>0 AND A[i]> key

DO A[i+1] <--> A[i]

A[i] <-- key

i <-- i-1

 

Running Time:
  • Depends on input
    • If input reverse sorted running time will be more
    • If input is already sorted running time will be minimum
  • Depends on input size.
    • Fast for small input size
    • Slow for input size is very large
  • Depends on computer
    • relative speed (same system)
    • absolute speed (different system)
Worst Case:

Scenario: When the input is reverse sorted.

T(n) = Ө(n2)


Selection Sort Algorithm

 
Input:

Sequence <A1', A2', ...An'> of numbers

Output:

Permutation of numbers

Pseudocode:

Permutation of numbers <A1',A2',...An'>

Description:
  1. Find first smallest element in array and move it to 1st position
  2. Find second smallest element and move it to 2nd position
  3. ...
  4. Repeat same until array is sorted
Running Time:

Space: O(1)

Worst Case:

O(n2)

Average Case:

O(n2)


Bubble Sort

Input:

Sequence <A1', A2', ...An'> of numbers

Output:

Permutation of numbers <A1',A2',...An'>

Description:
  • Swipe first two elements if the 1st element is greater
  • Swipe 2nd and 3rd element if 2nd element is greater
  • Repeat same until array is sorted
Running Time:

Space: O(1)

Worst Case:

O(n2)

Average Case:

O(n2)


Quick Sort

 
 
Worst Case:

O(n2)

Average Case:

O(n log(n))


Radix Sort Algorithm

Running Time:

O(np) , p:number of passes of sorting algorithm, n: number of elements