leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

sort-an-array.dart (1171B)

      1 //Given an input list nums sort the list in O(nlog(n)) time
      2 //without using the built in sort function. To do this I used
      3 //merge sort recursively which splits the list into n lists and then joins
      4 //them together.
      5 //Time: 505ms Beats: 44.44%
      6 //Memory: 210.2 MB Beats: 33.33%
      7 
      8 class Solution {
      9   List<int> sortArray(List<int> nums) {
     10       if(nums.length == 1){
     11         return [nums[0]];
     12       }
     13       List<int> l1 = sortArray(nums.sublist(0 , (nums.length / 2).toInt()));
     14       List<int> l2 = sortArray(nums.sublist((nums.length / 2).toInt()));
     15       List<int> l3 = [];
     16       int l1_pointer = 0;
     17       int l2_pointer = 0;
     18       while(l1_pointer < l1.length && l2_pointer < l2.length){
     19         int l1_val = l1[l1_pointer];
     20         int l2_val = l2[l2_pointer];
     21         if(l1_val < l2_val){
     22           l3.add(l1_val);
     23           l1_pointer += 1;
     24         }
     25         else{
     26           l3.add(l2_val);
     27           l2_pointer += 1;
     28         }
     29       }
     30       while(l1_pointer < l1.length){
     31           l3.add(l1[l1_pointer]);
     32           l1_pointer += 1;
     33       }
     34       while(l2_pointer < l2.length){
     35           l3.add(l2[l2_pointer]);
     36           l2_pointer += 1;
     37       }
     38       return l3;
     39   }
     40 }