Next, the first elements from each of the two lists are compared.

The lesser element is then removed from its list and added to the final result list.

Why divide & conquer ?

1) A small list will take fewer steps to sort than a large list.

2) Fewer steps are required to construct a sorted list from two sorted lists than from two unsorted lists.

package main.java.algo.sorting; public class MergeSort { public static void main(String[] args) { int[] data = {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}; MergeSort m = new MergeSort(); int[] sorted = m.mergeSort(data); for(int a: sorted) { System.out.println(a); } } /*** *** answer[] = ms ({18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}) left[] = ms ({18, 6, 9, 1, 4}) left[] = ms [{18, 6}) left[] = ms({18}) = 18 right[] = ms({6}) = 6 merge(left,right) = merge(18,6) = {6,18} right[] = ms ({9,1,4}) left[] = ms({9}) = 9 right[] = ms({1,4}) left[] = ms ({1}) = 1 right[] ms ({4}) = 4 merge(left,right) = merge(1,4) = {1,4} merge(left,right) = merge({9},{1,4}) = {1,4,9} merge(left,right) = merge({6,18},{1,4,9}) ={1,4,6,9,18} right[] = ms ({15, 12, 5, 6, 7, 11}) .... = {5,6,7,11,12,15} merge(left,right) = merge({1,4,6,9,18},{5,6,7,11,12,15}) = {1,4,5,6,7,9,11,12,15,18} *** *** ***/ public int[] mergeSort(int[] data) { // since it is recursion - always remember to write the base case if(data == null || data.length == 1) return data; int middleIdx = data.length/2; //start-index : inclusive, end-index : exclusive //Divide array into left & right till we reach the smallest array (with only one element) int left[] = mergeSort(subArray(data, 0, middleIdx)); int right[] = mergeSort(subArray(data, middleIdx, data.length)); //consider the array represented as a binary tree //then at every level - sort using merge sort. //when the recursion moves backwards - we sort smallest groups, merging them into bigger and so on.. till we get the elements in the input array. int res[] = merge(left, right); for(int a: res) { System.out.println(a); } System.out.println("==============="); return res; } /*** *** We merge from bottom to top, means smaller sub arrays gets merged (and sorted). *** On very 1st merge(..) call - there will be inly one element in input arrays. left={18} and right={6} gives sorted {6,18} and so on.. *** So left[] and right[] params at any point are sorted in itself and we need to merge them. *** Thus, the smallest element among left[] and right[] - must sit at top of one of the lists. *** It can be removed and put into result[]. The 2nd smallest again lies in the top position in one of the left or right arrays. *** After removing elements, if one list is exhausted - blindly copy the elements from the other list to the result. ***/ private int[] merge(int[] left, int[] right) { if (left == null || left.length == 0) return right; else if (right == null || right.length == 0) return left; int resultSize = left.length + right.length; int[] result = new int[resultSize]; int lIdx = 0, rIdx = 0, rsltIdx = 0; while (rsltIdx < resultSize) { if (rIdx == right.length) { result[rsltIdx] = left[lIdx]; lIdx++; } else if (lIdx == left.length) { result[rsltIdx] = right[rIdx]; rIdx++; } else if (left[lIdx] < right[rIdx]) { result[rsltIdx] = left[lIdx]; lIdx++; } else if (right[rIdx] < left[lIdx]) { result[rsltIdx] = right[rIdx]; rIdx++; } else { //same elements on top in left & right //moving only one element result[rsltIdx] = left[lIdx]; lIdx++; } rsltIdx++; } return result; } //start-index : inclusive, end-index : exclusive private int[] subArray(int[] data, int startIdx, int endIdx) { int[] subArray = new int[endIdx - startIdx]; //populating the sub-array //dataIdx < endIdx : since end-index is exclusive for (int dataIdx = startIdx, subArrayIdx = 0; dataIdx < endIdx; dataIdx++, subArrayIdx++) { subArray[subArrayIdx] = data[dataIdx]; } return subArray; } } // Sorting in-place - is possible but complicated -- use linklist instead of array /*** *** COMPLEXITY ANALYSIS *** *** MergeSort is a divide and conquer algorithm. *** *** If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2)... unto kth recurrence = 2^k T (n/2^k) *** *** Time Complexity - O(n log n) *** *** - Loop executes recursively log n times -- O(log n) *** - In Every loop, a merge function in called used to merge n elements ([k] and [n-k]) -- O(n) *** - Total = O(n) *** O(log n) = O(n log n) *** *** Space complexity = O(n) *** *** - O(n) - used in merge function for the result array *** - O(log n) - used in stack for log n recurrsive calls *** - O(n) + O(log n) = O(n) *** *** Best Case = O(n log n) *** *** *** Worst case = O(n log n) *** *** *** Average Case - O(n log n) *** *** *** ***/

**********************************************************************************

**Comparisons**

heapsort has same time complexity as merge sort, but requires O(1) space for sorting [once the heap is created], as compared to O(n) and is faster in implementation.

**********************************************************************************

**Sorting Linked list**

- Merge sort is best for any sequential data (lists, hard disks)

- It is easy to maintain merge sort that it requires only O(1) space.

- Coz of slow random access of linked list nodes -

- quick sort - performs poorly

- heap sort - impossible

**********************************************************************************

**Online Sorting**

Merge sort's merge operation is useful in online sorting, where the list to be sorted is received a piece at a time, instead of all at the beginning.

In this application, we sort each new piece that is received using any sorting algorithm, and then merge it into our sorted list so far using the merge operation.

However, this approach can be expensive in time and space if the received pieces are small compared to the sorted list — a better approach in this case is to

store the list in a self-balancing binary search tree and add elements to it as they are received.

**********************************************************************************

Merge sort parallelizes better; the most trivial way of parallelizing merge sort achieves close to linear speedup, while there is no obvious way to parallelize heapsort at all.

khóa học kế toán xây dựng

ReplyDeletekhóa học kế toán xây dựng

khóa học kế toán xây dựng

căn cứ tính thuế đối với thu nhập từ đầu tư vốn

cách tính thuế đối với thu nhập từ chuyển nhượng vốn

cách khấu trừ thuế thu nhập cá nhân

hướng dẫn quyết toán thuế tncn

hướng dẫn hoàn thuế tncn

hướng dẫn thuế tndn

sửa đổi về thuế tndn

miễn thuế thu nhập cá nhân

người nộp thuế tncn là những ai

hoàn thuế gtgt

báo cáo thuế quý gồm những gì

cách lập hóa đơn gtgt

cách đăng ký thuế thu nhập cá nhân

lưu ý khi thực hiện quyết toán thuế tncn

hướng dẫn sử dụng một số hàm cơ bản trong excel

Một số sai sót thường gặp khi hạch toán kế toán

một số sai sót kế toán và cách sửa chữa

mẹo tô màu xen kẽ các dòng trên bảng tính lớn trong Excel

cách mở nhiều bảng tính khác nhau trong Excel

mức phạt nộp chậm thuế gtgt

quy định mới về hóa đơn bán hàng