Regarding in-place merge in an array

by

This seems to indicate that it is possible to do in O(lg^2 n) space. I cannot see how to prove that it is impossible to merge in constant space, but I cannot see how to do it either.

Edit:
Chasing references, Knuth Vol 3 – Exercise 5.5.3 says “A considerably more complicated algorithm of L. Trabb-Pardo provides the best possible answer to this problem: It is possible to do stable merging in O(n) time and stable sorting in O(n lg n) time, using only O(lg n) bits of auxiliary memory for a fixed number of index variables.

More references that I have not read. Thanks for an interesting problem.

Further edit:
This article claims that the article by Huang and Langston have an algorithm that merges two lists of size m and n in time O(m + n), so the answer to your question would seem to be yes. Unfortunately I do not have access to the article, so I must trust the second hand information. I’m not sure how to reconcile this with Knuth’s pronouncement that the Trabb-Pardo algorithm is optimal. If my life depended on it, I’d go with Knuth.

I now see that this had been asked as and earlier Stack Overflow question a number of times. I don’t have the heart to flag it as a duplicate.

Huang B.-C. and Langston M. A., Practical in-place merging, Comm. ACM 31 (1988) 348-352

More Related Contents:

  1. How to sort in-place using the merge sort algorithm?
  2. Algorithm for all subsets of Array
  3. VBA array sort function?
  4. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  5. Given an array of numbers, return array of products of all other numbers (no division)
  6. Why is quicksort better than mergesort?
  7. Sorting a multidimensionnal array in VBA
  8. Preserve key order (stable sort) when sorting with PHP’s uasort
  9. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  10. Group array by subarray values
  11. Swift sort an array with strings and numbers [duplicate]
  12. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  13. Find elements of array one nearest to elements of array two
  14. `std::list::sort()` – why the sudden switch to top-down strategy?
  15. Maximum single-sell profit
  16. In-place array reordering?
  17. Sort an array according to the elements of another array
  18. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  19. How to sort an array of hashes in ruby
  20. find pair of numbers in array that add to given sum
  21. Interview question: three arrays and O(N*N)
  22. How to find repeating sequence of characters in a given array?
  23. Maximum sum of non consecutive elements
  24. Finding kth smallest number from n sorted arrays
  25. In Swift how can I sort one array based on another array?
  26. calculating the number of “inversions” in a permutation
  27. How does Array#sort work when a block is passed?
  28. Mergesort with Python
  29. Merge sort time and space complexity
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment