Java Interview Guide: How to Build Confidence With a Solid Understanding of Core Java Principles pdfdrive com

Merge Sort
Merge sort is a stable 
O(n log n)
average-case sorting algorithm. It works
by recursively dividing a list into individual sublists, and merging each sublist
together to produce a sorted result. Merge sort is an example of a divide and
conquer algorithm, which recursively reduces a problem to a trivial solution.

---

Quicksort
Quicksort is an unstable 
O(n log n)
average-case sorting algorithm. It works
by defining a pivot and swapping elements so that lesser values appear before
the pivot and greater values appear after the pivot. The remaining pivots are
sorted recursively. As of Java 7, quicksort is the default implementation for
sorting primitives in the 
Arrays
class.

---

Timsort
Timsort is a stable 
O(n log n)
average-case sorting algorithm. Timsort
is a hybrid algorithm derived from merge sort and insertion sort. It works
by identifying runs of naturally sorted data or by using insertion sort to create
runs of a minimum size. The runs are merged together in the same manner
as merge sort. Timsort often performs far fewer than 
O(n log n)
comparisons because it takes advantage of partially sorted values. As of Java 7,
Timsort is the default implementation for sorting objects in the 
Arrays
and
Collections
classes.

---

Questions
What is Big O notation? What are some common examples?
What is a binary search? How well does it perform?
What is insertion sort? How well does it perform?
What is merge sort? How well does it perform?
What is quicksort? How well does it perform?
What is timsort? How well does it perform?

---