Sorting Algorithm

Linear
Divide and Conquer

Performance Measure
Number of swaps
Number of comparison

Bubble Sort

• Compare each array item to it’s right neighbor
• If the right neighbor is smaller then Swap right and left
• Repeat for the remaining array items
• At the end of first iteration you will have largest number at the end
• For next iteration you don't have to consider last item for comparison, since it is already at the correct place.
• Follow above step until you perform no swap.
• Performance
• Worst Case: O(n2) - Not suitable for large unsorted data
• Average Case: O(n2) - Not suitable for large unsorted data
• Best Case : O(n) - Works best for already sorted or nearly sorted data
• Space Required: O(n)
• Reference

Insertion Sort

• Everything left of the current item being worked on is considered to be sorted
• If current item is greater than the last item in the sorted part, then current item is at the correct position.
• If above is not true then you find the correct position of the current item in the sorted part and then insert it at that location after shifting rest of shorted items by one towards right.
• Follow above step until end.
• Only one iteration
• Performance
• Worst Case: O(n2) - Not suitable for large unsorted data
• Average Case: O(n2) - Not suitable for large unsorted data
• Best Case : O(n) - Works best for already sorted or nearly sorted data
• Space Required: O(n)
• Reference

Selection Sort

• Enumerate the array from the first unsorted item to the end
• Identify the smallest item
• Swap the smallest item with the first unsorted item
• Performance
• Worst Case: O(n2) - Not suitable for large unsorted data
• Average Case: O(n2) - Not suitable for large unsorted data
• Best Case : O(n2) - Not suitable for large unsorted data. This does a lot of comparison because of that this has worst performance in best case scenarios also.
• Space Required: O(n)
• Reference

Merge Sort

• The dataset is recursively split in half until it contains one item.
• It is then merged in sorted order
• After this point sets are always sorted
• This is called divide and conquer
• Performance - This has predictable performance O(n log n) in all kind of scenarios which is different that other Linear sorting algorithm. This has also advantage of working in parallel.
• Worst Case: O(n log n) - Suitable for large unsorted data
• Average Case: O(n log n) - Suitable for large unsorted data
• Best Case : O(n log n) - Suitable for large unsorted data
• Space Required: O(n) - Merge can be, but is often not, performed in-place, meaning new data sets are created during split. These extra allocations increase the memory footprint required to sort data.
• Reference

Quick Sort

• Pick a pivot value
• Move every item small than pivot item towards it left and item greater than pivot item toward its right.
• At this point you know that pivot item is at the right location. 
• Perform this operation on items on both side of the pivot until everything is sorted
• Performance
• Worst Case: O(n2) - Not suitable for large inverse sorted data
• Average Case: O(n log n) - Suitable for average case
• Best Case : O(n log n) - Works best for already sorted or nearly sorted data
• Space Required: O(n)
• Reference