Big O notation

 Big O notation is used to classify algorithms according to how their run time or memory space requirements grow as the input size grows.

From chart, O(1) has the least complexity, and O(n!) is the most complex.

Time Complexity, An algorithm is said to be 

1) Constant time (also written as ${\textstyle O(1)}$ time) if the value of ${\textstyle T(n)}$ is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking ${\textstyle O(n)}$ time. 

2) logarithmic time when , commonly found on binary trees or binary search.
An example of logarithmic time is given by dictionary search. Consider a dictionary D which contains n entries, sorted by alphabetical order.

3)  Linear algorithm – O(n) – Linear Search. 

4)  Superlinear algorithm – O(n log n) – Heap Sort, Merge Sort. 

5) Polynomial algorithm – O(n^c) – Selection Sort, Insertion Sort, Bucket Sort. 

Space Complexity, measure the memory usage amount 

1) Ideal algorithm - O(1) - Linear Search, Binary Search, Selection Sort, Insertion Sort, Heap Sort.

2) Logarithmic algorithm - O(log n) - Top down merge sort for linked list .

3) Linear algorithm - O(n) - Quick Sort, Merge Sort with recursive merge.

4) Sub-linear algorithm - O(n+k) - Radix Sort.

Merge Sort can use consume O(log(n)), O(n) or O(1) stack space!!,
A top down merge sort for linked list will consume O(log(n)) stack space,
and it's slower than a bottom up approach due to scanning of lists to split them. merge sort can take O(n) stack space due to the recursive merge().
A bottom up merge sort for linked list uses a small (25 to 32) fixed size array of references (or pointers) to nodes, which would meet the O(1) space requirement.

Link to wiki article:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists