• Terminlogy
    • In place Sorting Algorithm -
    • Stable Sorting Algorithm - A sorting algorithm is stable, if it preserves the order of original records with equal keys
    • Internal Sorting Algorithm - A sorting algorithm is internal, if it works on lists in the internal memory
    • External Sorting Algorithm - A sorting algorithm is external, if it works on data in external files
    • Measure of input size - Length of array
    • Basic Operation - Comparison of elements
Sorting Method Technique Performance Suitable Datasets
Bubble Sort Comparing adjacent elements and swapping those out of order, from beginning to end. On each pass, the largest element bubbles to the end O(n^2) Use a flag to improve best case complexity
Selection Sort Select the largest element and place it at the end. Repeat for every pass O(n^2) Although identical to bubble sort, selection sort makes only 1 swap in each pass
Insertion Sort Take an element and insert it in the sorted portion of the array in each pass
Shell Sort Variaton of insertion sort
Heap Sort
Quick Sort Partition the data on a properly chosen pivot and recursively operate on the subarrays
Radix Sort
Merge Sort Recursively combine two sorted arrays into one O(nlogn) - avg case Large Data