Java HeapSort
I haven\'t seen any posts here using heapsort, despite it being reasonably good for sorting arrays in-place. A heap is a binary tree where a parent has a value 
I haven\'t seen any posts here using heapsort, despite it being reasonably good for sorting arrays in-place. A heap is a binary tree where a parent has a value greater than or equal to its children.\n\nBuilding a heap is nlogn. Each value is added as a leaf node, then it bubbles up the heap to its correct location. To turn a heap into a sorted array, remove the root (which is the current max value), replace it with a leaf node, then let the new root sink down to its correct location. This is also nlogn.\n\nedit: Thanks to [RodneyShag](https://leetcode.com/rodneyshag) for suggesting a significant optimization.\nRather than iteratively adding nodes to a heap, we can merge smaller heaps until only one is left. This ends up being O(n) for building the heap.\n\nImproved code: O(n) build heap, O(nlogn) convert heap to sorted array\n\n```Java\npublic static int[] heapSort(int[] nums) {\n\t//build the heap\n\tfor(int i=nums.length-1;i>=0;i--)\n\t\t//merge the 2 sub-heaps below i, by bubbling nums[i] down to the correct location\n\t\tsink(nums,i,nums.length);\n\t//turn it into a sorted list\n\tfor(int i=nums.length-1;i>0;i--){\n\t\t//remove the root, and put the last leaf at the root of the heap\n\t\tint tmp = nums[i];\n\t\tnums[i]=nums[0];\n\t\tnums[0] = tmp;\n\t\t//bubble the new root down to the correct location\n\t\tsink(nums,0,i);\n\t}\n\treturn nums;\n}\nstatic void sink(int[] nums, int start, int end){\n\tint val = nums[start];\n\tint i = start, next = 2*i+1;\n\twhile(next<end){\n\t\tif(next+1<end && nums[next+1]>nums[next])\n\t\t\tnext++;\n\t\tif(nums[next]<=val)\n\t\t\tbreak;\n\t\tnums[i]=nums[next];\n\t\ti=next;\n\t\tnext = 2*i+1; //2*i+1, 2*i+2 are the children of i\n\t}\n\tnums[i]=val;\n}\n```\n\nOriginal code: O(nlogn) build heap\n \n```Java\npublic static int[] heapSort(int[] nums) {\n\t//build the heap\n\tfor(int i=1;i<nums.length;i++){\n\t\tint val = nums[i];\n\t\tint j=i, next = (j-1)/2; //(j-i)/2 is the index of this location\'s parent\n\t\twhile(j>0 && nums[next]<val){\n\t\t\tnums[j]=nums[next];\n\t\t\tj=next;\n\t\t\tnext = (j-1)/2;\n\t\t}\n\t\tnums[j]=val;\n\t}\n\t\n\t//turn it into a sorted list\n\tfor(int i=nums.length-1;i>0;i--){\n\t\tint val = nums[i];\n\t\tnums[i]=nums[0];\n\t\t\n\t\tint j = 0, next = 1;\n\t\twhile(next<i){\n\t\t\tif(next+1<i && nums[next+1]>nums[next])\n\t\t\t\tnext++;\n\t\t\tif(nums[next]<=val)\n\t\t\t\tbreak;\n\t\t\tnums[j]=nums[next];\n\t\t\tj=next;\n\t\t\tnext = 2*j+1; //2*j+1, 2*j+2 are the children of j\n\t\t}\n\t\tnums[j]=val;\n\t}\n\treturn nums;\n}\n```
[]