Case: problem N° 912 of LeetCode about sorting a list of integers.
source: leetcode com/problems/sort-an-array/description/
I tried to solve it by using my own intuition and knowledge and after several tries and failures it turned out to be the tree algorithm but improved for cases where list is sorted already, with it my solution was accepted finally. According to measures of Leetcode my solution is not so fast like Merge sort but it is very efficient with the use of memory. So I reviewed merge sort algorithms provided by another participant and your book.
I made a comparison among my solution, another participant’s code, your code, and Dart’ sort. I’ve used for this comparison two arrays:
- First array (arr1): is an aray sorted of 50000 integers
- Second array (arr2): is an array unsorted of 50000 integers
My Solution
-
Original tree sort:
1.1 arr1: Building tree → 4640 ms, getting list → 11 ms ==> total: 4651 ms
1.2 arr2: Building tree → 11 ms, getting list → 10 ms ==> total: 21 ms -
Improved tree sort:
2.1 arr1: Building tree → 6 ms, getting list → 10 ms ==> total: 16 ms
2.2 arr2: Building tree → 17 ms, getting list → 12 ms ==> total: 29 ms
Another participant’s code
- arr1: 25 ms
- arr2: 30 ms
Your code
- Original code
1.1 arr1: 72 ms
1.2 arr2: 62 ms - Modified code (I replaced all generic types for an integer type)
2.1 arr1: 49 ms
2.2 arr2: 46 ms
Dart’s sort method
- arr1: 18 ms
- arr2: 36 ms
If we examine these results, your code can still be improved.