COSC 2320 Chapter Notes - Chapter 9-15: Big O Notation, Merge Sort, Quicksort
26 Feb 2017
School
Department
Course
Professor
Document Summary
Divides the array into 2 parts (high and low: an element of the array is selected as the pivot (can be any value in the array) Runtime: o(n log2 n) if pivot split the 2 parts equally, o(n log n) on average, o(n^2 in the worst case. This can be avoided by carefully choosing the pivot: worst case, there will be n-1 levels. Merge sort divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list i = first index: k = last index j = mid. Merge sort divides the input in half until a list of 1 element is reached. This requires log2 n partitioning levels: each level the algorithm does n comparisons. Abstract data type (adt) data type described by pre-defined user operations. List a common adt for holding ordered data. Node an item in a list.
