COMP 285 Study Guide - Midterm Guide: Merge Sort, Sorting Algorithm, External Sorting

• School: University of San Diego
• Department: Computer Science Courses
• Course: COMP 285
• Professor: Eric Jiang

Document Summary

Sorting many applications because many problems are reduced to sorting. Internal sorting requires all data to be sorted is in the main memory (ram) External sorting way too big to fit in main memory so extra data stored in hard disk. Simple straightforward in terms of coding -- carry quadratic complexity - o( Assumptions: array of objects with a field that can be compared with (key) Merge sort a divide and conquer approach; recursive based. More efficient than those simple sorting algorithms, but does require an extra array of size n -- can be generalized into an external (file) sorting algorithm. Halves the array, recursively sort its halves, then merge the halves. Better bc equal sized subarrays -- more efficient. Worst case = o( log n n. # of comparisons = n - 1. # of assignments = 2n (n - copying into temp and n - coping temp to a) Total = 2n + (n-1) = 3n - 1.