#Day3 #100DaysOfCode
implemented merge sort in array.
time complexity: O(nlogn)
divide and conquer algorithm
recommended use on linked list, more preferred on linked list than quicksort because
_insertion elements in linked lists is more efficient than in array. in linked list. it takes less time because we can just find the inserted position, break the list and insert element. While in array, we have to shift the whole array to the right to make space for the inserted element.
_mergesort access data sequentially just like linked list. there's no need for random access like in arrays.
we are able to merge subarrays just by specifying the index in merge function because the subarrays are continuous.
https://github.com/qbaocaca/data_structure_and_algorithm/blob/main/mergesort.cpp
implemented merge sort in array.
time complexity: O(nlogn)
divide and conquer algorithm
recommended use on linked list, more preferred on linked list than quicksort because
_insertion elements in linked lists is more efficient than in array. in linked list. it takes less time because we can just find the inserted position, break the list and insert element. While in array, we have to shift the whole array to the right to make space for the inserted element.
_mergesort access data sequentially just like linked list. there's no need for random access like in arrays.
we are able to merge subarrays just by specifying the index in merge function because the subarrays are continuous.
https://github.com/qbaocaca/data_structure_and_algorithm/blob/main/mergesort.cpp
